Description
You are playing a game. The goal of this game is to kill the monster when you are still alive (HP > 0, HP = health point). The monster is dead if and only if its HP <= 0.
This game consists of rounds, and you go first in each round.
You have 5 options in each round:
- ATTACK. This will deduct the monster's HP. If your damage point is p, then you can deduct p monster's HP.
- HEAL. You can recover some of your HP, but it can't exceed your max HP.
- Level-up. Level-up might enhance the effect of attacking or healing, but if you are not lucky enough, sometimes it will deduct the effect of attacking and healing. Thus, choosing to level-up is not always a good choice. If you have reached max level, taking this action makes no effect.
Besides, you are also given some potions (魔法藥水), which can be used to further increase your own capability or decrease the monster's capability. Specifically,
- Drink-potion. By drinking one bottle of potions, the effect of your next ATTACK or HEAL will be multiplied by 5. Note that: 1) this effect will only be applied once, and 2) consecutive drinking of several bottles of potions cannot stack the effect. If there are no remaining potions, this action cannot be performed.
- Throw-potion. Throwing one bottle of potions can add one layer of poisons (毒藥) on the monster to cause X points of damage to the monster, which will take effect starting from the next round and last for each of the following rounds (that is, the monster's HP will be deducted by X in each of these rounds) until the monster dies. Note that poisons can be accumulated, meaning that accumulated P layers of poisons in a given round will totally damage P * X points in that round. If there are no remaining potions, this action cannot be performed.
In each round, the monster will attack you once with a fixed amount of damage points.
You start the game with full HP, level 1 and K bottles of potions.
What is the minimun number of rounds you need to kill the monster? What is the sequence of actions to achieve the minimum number of rounds?
Additional Requirement: Since there could be multiple possible sequences of actions, output the lexicographically smallest string representation among all the possible sequences of actions. The conversion method is as follows: start with an empty string T, and then append the corresponding letters to the string T based on the action sequence. The letters are mapped as follows:
- ATTACK → 'A'
- HEAL → 'B'
- LEVEL-UP → 'C'
- DRINK POTION → 'D'
- THROW POTION → 'E'
Input
The first line of the input contains an integer T, representing the number of test cases (1 ≤ T ≤ 5).
For each of the T test cases, first line contains 7 numbers L, HP, MHP, MDMG, K, X, FLAG.
- L = max level
- HP = your max HP
- MHP = monster's HP in the beginning of game
- MDMG = monster's damage point
- K = amount of potions you have in the beginning
- X = damage point of each layer of poisons
- FLAG = 0 or 1. If FLAG = 1, you need to output the lexicographically smallest sequence of actions. If FLAG = 0, you don't.
Each of the next L lines describes each level, i-th line of them describing level i. Each of them consists of two numbers, DMG and HL.
- DMG = your damage point when you use ATTACK at level i
- HL = amount of HP you can recover when you use HEAL at level i
Limits:
- 1 ≤ L ≤ 10
- 1 ≤ HP ≤ 100
- 1 ≤ MHP ≤ 100
- 0 ≤ MDMG ≤ 10000
- 0 ≤ DMG ≤ 10000
- 0 ≤ HL ≤ 50
- 0 ≤ X ≤ 50
- 0 ≤ K ≤ 10
- FLAG = 0 or 1
Output
Print a single integer, denoting the mininum number of steps you need to kill the monster. If you are unable to beat the monster, print -1.
If FLAG = 1, output the sequence of actions to achieve it, each action in one line.
Test Case Constraints
- Testcases 1, 2: it is guaranteed that K = 0 and FLAG = 0.
- Testcase 3: it is guaranteed that X = 0 and FLAG = 0.
- Testcase 4: it is guaranteed that FLAG = 0.
- Testcase 5: it is guaranteed that X = 0 and FLAG = 1.
- Testcase 6: it is guaranteed that FLAG = 1.
Tags