CosmoCraft#3971
In the two-player game CosmoCraft, you manage an economy with the goal of building an army capable of defeating your opponent. You control the construction of workers, production facilities, and army units; the challenge is to balance the resources you allocate to each. The game progresses in turns.
Each worker provides income at the rate of dollar per turn.
Each production facility allows you to produce either a worker or an army unit for dollar per unit. (Only worker or army unit can be produced per turn per facility.)
It costs dollar to build a new production facility.
Your army units are required to fight your opponent.
You start with workers and production facilities. At each turn, you can spend your income obtained from workers on any mixture of workers, army units, and production facilities. Workers produced in the current turn do not contribute income until the next turn; likewise, production facilities built in the current turn do not become active until the next turn. Any unspent income carries over to the next turn.
At the end of each turn, you may use all the army units you have produced to attack your opponent. If you have strictly more army units than your opponent, your opponent immediately loses, and you keep the difference in army units. Otherwise, your army is destroyed, and your opponent keeps the difference in army units. (Your opponent may then counterattack, but you do not immediately lose in this case.) The game ends after turns, at which point both players usually attack with all their army units, and the player with the larger army is victorious.
You are playing against your friend and, since you have played together many times, you know exactly how your friend will spend money on every turn and exactly when each attack will occur. Knowing this, you decide that the best strategy is to play defensively—you simply wish to survive every attack, and to amass the largest possible army in the meantime to counterattack (and hopefully win) at the end of the game.
What is the largest number of army units you can have at the end of the game, given that you must survive all your friend's attacks?
The input contains several test cases. Each test case begins with a line containing three integers:
n k t
where (1 \le n \le 100) is the number of workers you start with, (1 \le k \le 100) is the number of production facilities you start with, and (1 \le t \le 10000) is the number of turns. The next line contains t-1 integers, a_i (0 \le a_i \le Max signed -bit integer), separated by spaces. The -th integer denotes the strength of the attack (the number of army units your opponent uses in that attack) on turn . The input ends with a line containing three s.
For each test case, output a single integer indicating the maximum number of army units you can have at the end of the game. Output if it is impossible to survive all attacks. Output each number on its own line, with no spaces, and do not print any blank lines between answers. Although some test cases may allow extremely large answers, all judge inputs produce answers that fit in a signed -bit integer.
Example 1