C - Code Art Online Editorial /

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