CosmoCraft

In the two-player strategy game CosmoCraft you build up an economy so that you can field an army strong enough to defeat your opponent. You manage workers, production facilities, and army units, and the whole game is about how you divide your money among them. The game is played in turns.

• Each worker gives you an income of 1 dollar per turn.
• Each production facility can, once per turn, produce either one army unit or one worker, at a cost of 1 dollar (a single facility makes at most one unit per turn).
• Creating a new production facility costs 1 dollar.
• Your army is what you fight your opponent with.

You start with $n$ workers and $k$ production facilities. On each turn you first collect income equal to your current number of active workers (added to any money carried over from earlier turns), and then you may spend that money on any mix of new workers, new army units, and new production facilities. Workers and facilities created on a turn only become active on the next turn, while army units are available immediately. Any money you do not spend carries over to the next turn.

The opponent attacks you at the end of each of the first $t-1$ turns. To survive the attack of strength $a_i$ on turn $i$, the number of army units you have at that moment must be at least $a_i$; surviving then removes $a_i$ units from your army (you keep the surplus). If you have fewer than $a_i$ units you are defeated. The game lasts $t$ turns, and there is no incoming attack on the final turn.

You have faced this opponent so often that you know exactly how strong each of their attacks will be. You decide to play purely defensively: survive every attack while stockpiling the largest possible army for a final counterattack. What is the largest army you can have at the end of the game if you must survive all of the opponent's attacks?

The input contains several test cases. Each test case begins with a line of three integers:

n k t

where $n$ ($1 \le n \le 100$) is the number of workers you start with, $k$ ($1 \le k \le 100$) is the number of production facilities you start with, and $t$ ($1 \le t \le 10000$) is the number of turns. The next line contains $t-1$ integers $a_i$ ($0 \le a_i \le 2^{63}-1$) separated by single spaces, where $a_i$ is the strength of the opponent's attack (the number of army units they use) at the end of turn $i$. The input ends with a line containing three zeros.

For each test case, output a single integer: the largest army you can have at the end of the game. Output $-1$ if it is impossible to survive every attack. Print each answer on its own line, with no extra spaces and no blank lines between answers. Every valid input is guaranteed to yield an answer that fits in a signed 64-bit integer.