Defend the Destiny Base

In Honkai Impact 3rd, the Valkyries defend a vital resource at the Destiny Base while battling a boss. The base is connected by a road of n cells. The boss starts at cell 0 and moves toward the resource at cell n at a base speed of 1 cell per second. The Valkyrie starts at cell 1. She will only attack the boss when the boss reaches her cell. Immediately after attacking the boss, she retreats one cell (i.e. her cell number increases by 1) so she may use a different attack mode. Each cell is equipped with one of the following eight attack modes, which not only deal instantaneous damage but also apply additional effects to the boss.

Attack modes:

1. Skill: Inflicts \(0.8\times atk\) damage and applies 1 layer of burning. Each burning layer deals an extra \(0.1\times atk\) damage per second.
2. Dodge: Inflicts \(0.7\times atk\) damage and pauses the boss for 5 seconds (the boss does not move during pause, but burning damage continues).
3. Ultimate: Inflicts \(1.2\times atk\) damage and pauses the boss for 5 seconds.
4. Branch Attack: Inflicts \(0.7\times atk\) damage and increases the transit time per cell by 1 second for the rest of the battle.
5. Love Bomb: Applies 1 layer of burning and increases the boss's speed by 50% (i.e. multiplies its speed by 1.5). It does no immediate damage.
6. Judas' Vow: Inflicts \(0.6\times atk\) damage; if the boss has any burning layers, one layer is removed; also pauses the boss for 4 seconds.
7. Otto's Light: Inflicts \(0.1\times atk\) damage; if the boss has burning layers, all burning layers are removed; and pauses the boss for 10 seconds.
8. Authority of the Just: Inflicts \(0.8\times atk\) damage and doubles the boss's speed (i.e. increases its current speed by 100%).

Between attacks the boss advances cell by cell. The time to traverse one cell is given by \(\frac{1}{speed}+ delay\), where speed is the boss’s current speed and delay is an extra time (initially 0) that is permanently increased by attack mode 4. In addition, if the boss is paused, it does not advance until the pause time elapses. Burning damage is applied at every full second that passes, regardless of whether the boss is moving or paused.

The battle ends in one of two ways:

• If the boss’s HP drops to 0 or below before it reaches the resource (i.e. before its cell reaches n), the battle is won. In this case, output the cell number at which the boss dies (this is the Valkyrie’s current cell where the finishing attack occurred).
• If the boss reaches cell n (touches the resource) before being defeated, output the maximum total damage dealt to the boss throughout the battle.

The initial parameters atk (the Valkyrie’s attack power) and hp (the boss’s health) are given. The planned strategy is provided as a sequence of n integers (each between 1 and 8), one for each cell from 1 to n, determining the attack mode the Valkyrie will use when the boss reaches that cell.

inputFormat

The first line contains three space‐separated numbers: atk, hp, and n.

The second line contains n integers, each between 1 and 8, representing the attack mode for cells 1 to n.

outputFormat

If the Valkyrie can defeat the boss before it reaches the resource, output the cell number at which the boss dies (i.e. the current Valkyrie cell when the final blow is delivered). Otherwise, output the maximum damage dealt to the boss.

sample

100 500 5
3 1 2 4 6

3