会津魔法学校は, 魔法を使える者が集まる学校である. その学校の生徒の一人であるハルカは, 魔法陣の上でワープの魔法を使う事ができる.
彼女の家から学校には, 長さ L の一直線状の道がある. また, この道には所々魔法陣が描かれている.
彼女は毎日この道を使って学校に通っているため, できるだけ短い時間で学校に辿り着きたいと思っている.
そこでプログラマーであるあなたは, 彼女に学校まで行くときにかかる最小の時間を教えてあげることにした.
ハルカは, 1 分で距離 1 だけ歩いて先に進むことができる ( *戻ることはできない).また, ワープの魔法陣が書いてある位置 Pi で魔法を唱えることで, Pi からちょうど Di だけ進んだ場所に Ti 分で移動することができる. 移動先に魔法陣がある場合も, 連続してワープ魔法を使用することができる.
彼女の家の位置は 0、学校の位置は L である.
L n P1 D1 T1 P2 D2 T2 . . Pn Dn Tn
1行目に道の長さ L, 魔法陣の数 n が与えられる. 次に n 個の魔法陣の状態が与えられる. Pi は i 番目の魔法陣がある位置, Di は i 番目の魔法陣からワープする距離, Ti は i 番目の魔法陣を使ってワープしたときにかかる時間を表す.
入力は以下の条件を満たす.
学校に辿り着くための最小の時間を一行に出力せよ.
10 3 2 2 1 4 2 1 8 1 1
8
10 2 2 3 1 3 5 1
6
1 0
1