50160. Skills

I'm a slow walker, but I never walk backwards.

Task Description

We will kill dragons with attack skills. We have four skills to attck the dragon, including three special attacks $A$, $B$, $C$, and one normal attack. A normal attack has a base damage. Each special attack has a base damage $b$, plus extra damage $e$, and a cooldown $c$.

We first describe how to play this game. For each round from 0 to $R - 1$, we choose the skill that will cause the maximum damage to attack the dragon. We can use a noraml attack at every round and cause its base damage, but not for special skills since they have cool downs. That is, there are two cases for when we can use a special attack. For the first special attack of a particular kind, we can use it at any round. For the second time and after, we can use a special attack at round $r$ only if $r - r'$ is at least its cool down $c$, where $r'$ is the last round we used that special attack.

The damage calculation is a little bit complicated for special attacks. If the player uses a special attack at round $r$ for the first time, there are two cases. If $r \leq c$, the skill causes base damage $b$. If $r > c$, the skill causes $b + e (r - c)$ damage. However, if the player uses a special attack at round $r$ for the second time or later, the damage is $b + e (r - r' - c)$, where $r'$ is the last time that special attack was used. Note that $(r - r' -c)$ is always non-negative since this is necessary for using the special attack.

The game will go for at most $R$ rounds. First you have to choose a skill that causes the maximum damage to the dragon. If there are more than one skill having the maximum damage, choose one in the order of $A$, $B$, $C$, then the normal attack. Second, subtract the damage from the dragon’s health. If the dragon’s health is still positive, the dragon lives and we add $g$ to its health, to the maximum of $H$. That is, if the health exceeds $H$, then it becomes $H$. On the other hand, if the health becomes 0 or negative after the attack, the dragon dies and we report that the game ends.
You need to output the health of the dragon after the damage and before adding $g$ at each round.

Let us explain the process by an example. We assume that $H = 20$, $g = 1$, and $R=30$. Also the information of the attack skills are listed below.

base damage extra damage cool down
special attack A 4 1 2
special attack B 3 1 2
special attack C 2 1 2
normal attack N 1 X X

When $r$ is 0, attack $A$ causes damage 4, attack $B$ causes 3, attack $C$ causes 2, and the normal attack causes 1, so we choose A. The dragon’s health becomes $20 - 4 = 16$ so you output 16. After that, the dragon will regent 1 health and it becomes 17.

When $r$ is 1, attack $A$ is in cool down and can be used again at or after $r=2$. Attack $B$ has damage 3, attack $C$ has 2, and the normal attack has 1, so we choose $B$. The dragon’s health becomes $17 - 3 =14$, and we output 14. After that, the dragon will regent 1 health and it becomes 15.

When $r$ is 2, attack $B$ is in cool down. Attack $A$ can be used again,and its damage is 4. Attack $C$ has damage 2, and the normal attack has damage 1, so we choose $A$. The dragon’s health becomes $15 - 4 =11$ and we output 11. Then the dragon will regent 1 health and it becomes 12.

When $r$ is 3, attack $A$ is in cool down, attack $B$ can be used again and it has damage 3. Attack $C$ has damage $2 + 1 *(3-2) = 3$ because it has extra damage at this round. Attack B and C has the same damage, so we choose B according to the priority. The dragon's health becomes $12 -3 = 9$, and we output 9. Then the dragon will regent 1 health and it becomes 10.

The game will repeat for $R$ rounds or dragon’s health becomes 0 or negative during the game.

Input Format

There will be 6 lines in the inputs. The first line is a positive integer $R$. The second line contains two integers, $H$ and $g$, which are dragon's maximum health points and the health regent at the end of every round. Each of the following three lines contains three integers. Each line has a special attack’s base damage $b$, extra damage $e$, and cooldown $c$. The 6th line is a positive integer, which is normal attack’s base damage.

  • $R, H, b, c \geq 1$
  • $g, e \geq 0$

Output Format

Output the health of the dragon after the damage and before adding $g$ at each round.

Subtask

  • 30 points : Three special attack's extra damage $e$ are all 0.
  • 70 point : Three special attack's extra damage could be positive integer or 0.

    Sample Input 1

    30
    20 1
    4 0 3
    3 0 3
    2 0 2
    1

    Sample Output 1

    16 14 13 10 8 7 4 2 1 -2

    Sample Input 2

    30
    20 1
    4 1 2
    3 1 2
    2 1 2
    1

    Sample Output 2

    16 14 11 9 6 2 -1

Discussion