Battle Simulation: Minimum Rounds to Defeat the Monster

Little \(X\) is playing a game where a warrior fights a single monster. The warrior starts with a health of \(iH\) and an attack power of \(iA\), while the monster has a health of \(H\). The battle is turn‐based with a maximum of \(M\) turns. If the monster is not defeated within \(M\) turns, \(X\) fails.

Each turn consists of two phases. In the first phase, the warrior takes action, and in the second phase, the monster acts if it is still alive. On the warrior’s turn, he can choose one of the following actions:

• Attack: The monster’s health is decreased by the warrior’s current attack power.
• Sharpen: The warrior increases his attack power by \(dA\).

After the warrior’s action, if the monster is still alive, it retaliates by attacking. In the \(i\)-th turn, the monster deals \(C_i\) damage to the warrior. If the warrior's health becomes less than or equal to zero after the monster's attack, he dies but is immediately revived; his health and attack power are reset back to the initial values \(iH\) and \(iA\) respectively (thus, any accumulated attack power boost is lost).

The battle ends immediately if, after a warrior's attack, the monster's health becomes \(\le 0\). Determine the minimum number of turns required for the warrior to defeat the monster. If it is impossible to defeat the monster within \(M\) turns, output \(-1\).

inputFormat

The first line contains five integers \(iH\), \(iA\), \(dA\), \(H\), and \(M\) which represent the warrior’s initial health, initial attack power, the attack increment from sharpening, the monster’s health, and the maximum number of turns respectively.

The second line contains \(M\) integers \(C_1, C_2, \ldots, C_M\), where \(C_i\) is the damage dealt by the monster on the \(i\)-th turn.

outputFormat

Output a single integer: the minimum number of turns required to defeat the monster, or \(-1\) if it is impossible.

sample

10 5 3 15 5
4 4 4 4 4

3