AT_ahc055_a [AHC055A] Weakpoint

"Nihonbashi Treasure Island" is a hugely popular novel in the fictional country R, and you are a big fan of the game based on this novel. In this game, numerous treasure boxes appear. Opening a treasure box allows you to acquire a weapon, which you can use to gain an advantage in the game. To open a treasure box, you must attack it using either your bare hands or a weapon. Having heard that a secret ending is unlocked by opening all the treasure boxes in the game, you decide to find a way to open all of them with the minimum number of attacks, hoping to see the ending as soon as possible. ### Problem Statement There are $ N $ treasure boxes, and the $ i $ -th treasure box is called treasure box $ i $ $ (0 \le i \lt N) $ . The initial hardness of treasure box $ i $ is $ H_i $ . Treasure box $ i $ contains weapon $ i $ . When the hardness of treasure box $ i $ is reduced to $ 0 $ or less, treasure box $ i $ opens, and weapon $ i $ becomes available. Weapons have durability, and the durability of weapon $ i $ is $ C_i $ . You can attack a treasure box using either your bare hands or an available weapon. - Attack with bare hands: When you attack treasure box $ b $ with your bare hands, the hardness of treasure box $ b $ is reduced by $ 1 $ . There is no limit to the number of bare-handed attacks. - Attack with a weapon: When you attack treasure box $ b $ with weapon $ w $ , the hardness of treasure box $ b $ is reduced by $ A_{w,b} $ , and the durability of weapon $ w $ decreases by $ 1 $ . When the durability of weapon $ w $ reaches $ 0 $ , it breaks and can no longer be used for attacks. Find a sequence of attacks to open all the treasure boxes with as few attacks as possible.

N/A

Input will be provided from Standard Input in the following format. ``` \( N \\ H_0 ~ H_1 ~ \ldots ~ H_{N-1} \\ C_0 ~ C_1 ~ \ldots ~ C_{N-1} \\ A_{0,0} ~ A_{0,1} ~ \ldots ~ A_{0,N-1} \\ A_{1,0} ~ A_{1,1} ~ \ldots ~ A_{1,N-1} \\ \vdots \\ A_{N-1,0} ~ A_{N-1,1} ~ \ldots ~ A_{N-1,N-1} \) ``` - $ N $ is the number of treasure boxes. It is fixed at $ N = 200 $ in all test cases. - The second line contains $ N $ space-separated integers $ H_0, H_1, \ldots, H_{N-1} $ representing the initial hardness of the treasure boxes. The hardness of treasure box $ i $ is $ H_i $ , satisfying $ 100 \leq H_i \leq 500 $ . - The third line contains $ N $ space-separated integers $ C_0, C_1, \ldots, C_{N-1} $ representing the durability of the weapons. The durability of weapon $ i $ is $ C_i $ , satisfying $ 1 \leq C_i \leq 6 $ . - The following $ N $ lines each contains $ N $ space-separated integers, $ A_{i, j} $ . - $ A_{i,j} $ represents the value by which the hardness of treasure box $ j $ is reduced when attacked with weapon $ i $ , satisfying $ 1 \leq A_{i,j} \leq 500 $ . ### Output Let $ T $ be the total number of attacks on the treasure boxes. Output $ T $ lines. ``` \( W_{0}~B_{0}\\ \vdots \\ W_{T-1} ~ B_{T-1} \) ``` For each line, output the weapon index $ W_i $ used for the $ i $ -th attack and the treasure box index $ B_i $ being attacked, in that order, separated by a space. If the $ i $ -th attack was performed with bare hands, $ W_i $ should be output as `−1`. [show example](https://img.atcoder.jp/ahc055/ys4u9l6aru.html?lang=en&output=sample)

N/A

### Scoring Your score is \\( \\sum\_{i=0}^{N-1} H\_i - T + 1 \\), where $ T $ is the number of attacks performed to open all treasure boxes. If the following invalid outputs are produced, it will be judged as WA. - Attacking an already opened treasure box - Attacking with a weapon that is not yet available - Attacking with a weapon whose durability has reached $ 0 $ - Outputting an invalid weapon number or treasure box number - Leaving any unopened treasure boxes after all attacks are finished There are $ 150 $ test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time. ### Input Generation - $ \mathrm{rand}(L, U) $ : Generates an integer uniformly at random between $ L $ and $ U $ , inclusive. - $ \mathrm{rand\_double}(L, U) $ : Generates a real number uniformly at random between $ L $ and $ U $ , inclusive. Generate $ H_i $ , $ C_i $ , and $ A_{i,j} $ $ (0 \le i \lt N, 0 \le j \lt N) $ independently, as follows: - $ H_i = \mathrm{rand}(100, 500) $ - $ C_i = \mathrm{rand}(1, 6) $ - $ A_{i,j} = \mathrm{round}(500.0 / \mathrm{rand\_double}(1.0, 500.0)) $ ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/ahc055/ys4u9l6aru.html?lang=en): This is more powerful than the local version providing animations. - [Local version](https://img.atcoder.jp/ahc055/ys4u9l6aru.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc055/ys4u9l6aru_windows.zip): If you are not familiar with the Rust language environment, please use this instead. Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.