Problem D
A Winning Strategy?

Suppose we have a simple betting game where a single player bets on whether a coin flip will produce heads or tails. More specifically, the game is divided into $n$ rounds ($1 \leqslant n \leqslant 1,000$), where the money available at the start of each round is denoted as $m_ i$ and the bet amount is denoted as $b_ i$. The outcome of each round is determined by the flip of a fair coin. The rules of the game are as follows:

• $1 \leqslant m_1 \leqslant 1,000$
  Players must start the game with at least $1 and at most $1,000.

• $1 \leqslant b_ i \leqslant m_ i$
  On any given round, you can’t bet more money than you have at the start of that round.

• If the outcome of round $i$ is heads, then $m_{i+1} = m_ i + b_ i$.

• If the outcome of round $i$ is tails, then $m_{i+1} = m_ i - b_ i$.

• The game ends once all $n$ rounds have been played or if, in any given round $i$, $m_ i = 0$ (the player is broke and can’t continue playing).

In the 18th century, French gamblers tried to come up with a winning strategy for this game and others with similar rules. They came up with a strategy called the martingale, where the player chooses an initial bet $b_1$ and then updates $b_ i$ in subsequent rounds based on the result of the previous round. More specifically:

• If the player lost round $i$ (i.e., the coin flip produced tails), then $b_{i+1} = \min (2\cdot b_ i, m_{i+1})$.

• If the player won round $i$ (i.e., the coin flip produced heads), then $b_{i+1} = \min (b_1, m_{i+1})$.

The intuition behind this strategy is the following: if you lose a round, you want to recover those loses and still make a profit if you win the next round, so you double the bet amount (without exceeding the amount of money on hand). However, once you win a round, you want to return to a less aggressive betting strategy, and return to betting the initial bet amount $b_1$ (without exceeding the amount of money on hand).

For example, if you had $100 and bet $20, but lost the bet, you would be left with $80. According to the martingale rules, you would now bet $40 and, if you won, you would have $120 (you recovered your loses and made an extra $20). Of course, if you lost the second round too, you would be down to $40.

Here is a more complete example, for a game with $n=4$ rounds, $m_1=100$, and $b_1=5$.

At the end of this game, the player has $90.

Here is a different example, where the player ends up going broke ($n=8$, $m_1=140$, $b_1=20$).

Notice how, even though the game had more rounds, the game ends after the third round because the player has no more money to bet.

So, although the martingale strategy can be effective in quickly recovering from a loss, it can also make the player go broke much faster. In fact, it has been shown that a martingale strategy can only be effective with infinite wealth and time.

You will write a program that, given values for $n$, $m_1$, and $b_1$, will compute the outcome of the game according to the martingale betting strategy described above.

Input

The input contains the specification of a single game. The first three lines contain the values of $m_1$, $b_1$, and $n$, respectively. The fourth line contains $n$ integers, each separated by a single space. These integers specify the outcome of the $n$ coin flips in the game: a 1 indicates heads, and a 0 indicates tails.

Note that the first two sample inputs correspond to the two examples shown above.

Output

The output contains a single line with the result of the game. If the player goes broke, print BROKE. Otherwise, print a single integer with the amount of money that the player has at the end of the game (i.e., $m_{n+1}$)

100
5
4
0 1 0 0

90

140
20
8
0 0 0 1 0 1 1 1

BROKE

100
5
4
1 1 1 1

120