Time Limit: 2 sec / Memory Limit: 256 MB
問題文
Code Art Online は符号の世界のRPGです。 プレーヤーは符号を生成して戦います。 符号は文字を連ねることで生成します。
このゲームには、あなたの操作する プレーヤー と、プレーヤーに立ちはだかる 敵 という2種類のキャラクターが登場します。
1 ターンは、敵の攻撃、プレーヤーの攻撃、敵の回復、プレーヤーの回復の順に行われます。
ゲーム開始時のプレーヤーの HP(体力)は 100 であり、これが 0 以下になるとゲームオーバーです。
あなたは、プレーヤーを以下の3種類の文字を使って操作することができます。
-
A
: 敵の HP に 5 ダメージを与える -
B
:B
が連続した数だけ敵の HP にダメージを与える -
C
: プレーヤーの HP を 50 回復する
BBB
と操作すると、1 ターン目に 1 ダメージ、2 ターン目に 2 ダメージ、3 ターン目に 3 ダメージを敵の HP に与えます。プレーヤーの最大 HP は 100 であり、これを超えて回復しようとした場合には HP は 100 となります。
同一ターン内の被ダメージ処理と回復処理は被ダメージ処理の方が先に行われるので、被ダメージ処理が終わった段階で HP が 0 以下になった場合、その時点でゲームオーバーとなります。
敵には最大 HP と攻撃力と回復力のパラメーターがあります。
敵の HP は現れた時には最大 HP と同じ値です。
毎ターンに攻撃力の値だけプレーヤーの HP にダメージを与え、回復力の値だけ HP を回復します。
ただし、最大 HP を超えて回復しようとした場合は、HP は最大 HP と同じ値になります。
敵の回復処理はプレーヤーと同じく被ダメージ処理の後に行われるので、被ダメージ処理が終わった段階で HP が 0 以下になった場合、回復は行われずその敵は倒れます。
敵が複数存在する場合、戦っている敵を倒すと自動的に次の敵が現れ、次のターンにはその敵と戦うことになります。
例えば、敵が 2 体いて、1 体目の敵の HP が 10、攻撃力が 15、回復力が 1 であり、2 体目の敵の HP が 20、攻撃力が 10、回復力が 2 であるとします。
この時、AAACBBBBBB
という符号で戦えば、次のように 2 体の敵を倒すことができます。
ターン 符号 プレーヤーHP 敵HP 1 A 85 6 2 A 70 2 3 A 55 0 # 一体目の敵を撃破 4 C 95 20 # プレーヤーは10ダメージを受けた後に50回復する 5 B 85 20 # 敵は1ダメージ受けた後に1回復する 6 B 75 20 # 敵は2ダメージ受けた後に2回復する 7 B 65 19 8 B 55 17 9 B 45 14 10 B 35 10 11 B 25 5 12 B 15 0
敵の数とそれぞれの敵の HP、攻撃力、回復力を与えるので、すべての敵をゲームオーバーせずに最短ターン数で倒す符号の長さを答えなさい。
入力
N a_1 b_1 c_1 : a_N b_N c_N
- 1 行目には敵の数 N (1 \leq N \leq 30) が与えられます。
- 2 行目から N+1 行目までには、それぞれの敵の HP a_i (1 \leq a_i \leq 100)、攻撃力 b_i (0 \leq b_i \leq 100)、回復力 c_i (0 \leq c_i \leq 100) がスペース区切りで与えられます。
出力
敵を倒すことが不可能であれば、
-1
を出力せよ。なお、行の終端には改行が必要である。
入力例 1
2 10 15 1 20 10 2
出力例 1
10
入力例 2
5 63 15 11 15 5 3 67 17 11 21 4 5 43 8 10
出力例 2
-1
入力例 3
9 64 1 0 89 3 3 91 4 0 99 0 3 32 2 0 10 3 1 82 1 3 1 1 2 8 5 0
出力例 3
37