{"problem":{"name":"H. Commandos","description":{"content":"A commando is a soldier of an elite light infantry often specializing in amphibious landings, abseiling or parachuting. This time our Commando unit wants to free as many hostages as it could from a ho","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10114H"},"statements":[{"statement_type":"Markdown","content":"A commando is a soldier of an elite light infantry often specializing in amphibious landings, abseiling or parachuting. This time our Commando unit wants to free as many hostages as it could from a hotel in Byteland, This hotel contains 10 identical floors numbered from 1 to 10 each one is a suite of 10 by 10 symmetric square rooms, our unit can move from a room (F, Y, X) to the room right next to it (F, Y, X + 1) or front next to it (F, Y + 1, X) and it can also use the cooling system to move to the room underneath it (F - 1, Y, X).\n\nKnowing that our unit parachuted successfully in room 1-1 in floor 10 with a map of hostages locations try to calculate the maximum possible hostages they could save.\n\nYour program will be tested on one or more test cases. The first line of the input will be a single integer T. Followed by the test cases, each test case contains a number N (1 ≤ N ≤ 1, 000) representing the number of lines that follows. Each line contains 4 space separated integers (1 ≤ F, Y, X, H ≤ 10) means in the floor number F room Y-X there are H hostages.\n\nFor each test case, print on a single line, a single number representing the maximum possible hostages that they could save.\n\n## Input\n\nYour program will be tested on one or more test cases. The first line of the input will be a single integer T. Followed by the test cases, each test case contains a number N (1 ≤ N ≤ 1, 000) representing the number of lines that follows. Each line contains 4 space separated integers (1 ≤ F, Y, X, H ≤ 10) means in the floor number F room Y-X there are H hostages.\n\n## Output\n\nFor each test case, print on a single line, a single number representing the maximum possible hostages that they could save.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ N_k \\in \\mathbb{Z} $ denote the number of hostage locations.  \n- Let $ L_k = \\{(f_i, y_i, x_i, h_i) \\mid i \\in \\{1, \\dots, N_k\\} \\} $ be the set of hostage locations, where:  \n  - $ f_i \\in \\{1, \\dots, 10\\} $: floor number,  \n  - $ y_i \\in \\{1, \\dots, 10\\} $: row coordinate,  \n  - $ x_i \\in \\{1, \\dots, 10\\} $: column coordinate,  \n  - $ h_i \\in \\{1, \\dots, 10\\} $: number of hostages at $ (f_i, y_i, x_i) $.  \n\nThe commando starts at position $ (10, 1, 1) $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{unknown} $ (implied by input format)  \n2. For each test case:  \n   - $ 1 \\le N_k \\le 1000 $  \n   - $ 1 \\le f_i, y_i, x_i, h_i \\le 10 $ for all $ i $  \n\n**Objective**  \nFind the maximum sum of hostages $ \\sum h_i $ that can be collected along a path starting at $ (10, 1, 1) $, moving only to adjacent rooms:  \n- Same floor: $ (f, y, x) \\to (f, y, x+1) $ or $ (f, y+1, x) $,  \n- Down one floor: $ (f, y, x) \\to (f-1, y, x) $,  \nwith no upward movement allowed.  \n\nFormally, define a directed graph $ G_k = (V_k, E_k) $:  \n- $ V_k = \\{(f, y, x) \\mid f,y,x \\in \\{1,\\dots,10\\}\\} $,  \n- $ E_k $ contains edges:  \n  - $ (f, y, x) \\to (f, y, x+1) $ if $ x < 10 $,  \n  - $ (f, y, x) \\to (f, y+1, x) $ if $ y < 10 $,  \n  - $ (f, y, x) \\to (f-1, y, x) $ if $ f > 1 $.  \n\nEach vertex $ (f, y, x) $ has weight $ w(f, y, x) = \\sum \\{ h_i \\mid (f_i, y_i, x_i) = (f, y, x) \\} $.  \n\nCompute the maximum weight path from $ (10, 1, 1) $ to any reachable vertex in $ G_k $.  \n\n**Output**  \nFor each test case, output the maximum total hostages collectible along such a path.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10114H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}