問題文

KowerKoint 君は音楽ゲームが好きです。 KowerKoint 君は、このゲームのとある曲で、できるだけ簡単にちょうど X のスコアを得たいと考えています。

この曲では M 個のリズムアイコンが流れてきます。KowerKoint 君はこれらのリズムアイコンをそれぞれ 1 回以下の回数タップすることができます。曲の開始時スコアは 0 で、 i 番目のリズムアイコンをタップすると、 S_i のスコアを得ることができます。

また、 1 \leq j \leq K に対し、 a_j 番目から b_j 番目までのリズムアイコンをすべてタップすることの難易度は c_j です。

スコアをちょうど X にできるかを判定し、ちょうど X にできるならば、達成する必要のある難易度の最大値としてありうる最小値を求めてください。ただし、任意の j について a_j 番目から b_j 番目までのリズムアイコンのどれかはタップせずに合計スコアをちょうど X にできる場合、難易度の最大値は 0 とします。

制約

• 1 \leq X \leq 10{,}000
• 1 \leq M \leq 1{,}000
• 1 \leq K \leq \min(200{,}000,\frac{M(M+1)}{2})
• 1 \leq S_i \leq 10^{9}
• 1 \leq a_j \leq b_j \leq M
• (a_1,b_1),(a_2,b_2),\dots,(a_K,b_K) は相異なる
• 1 \leq c_i \leq 10^{9}
• 入力はすべて整数

小課題

1. ( 1 点) a_j=b_j

2. ( 99 点) 追加の制約はない

入力例 1

7 4 3
3 2 2 3
1 2 10
2 3 3
3 4 20

出力例 1

10

4 番目以外のリズムアイコンをタップするのが最適です。

このテストケースは小課題 1 の制約を満たしません。

入力例 2

9 4 3
3 2 2 3
1 2 10
2 3 3
3 4 20

出力例 2

-1

スコアをちょうど 9 にすることはできません。

このテストケースは小課題 1 の制約を満たしません。

入力例 3

7 4 3
3 2 2 3
1 1 10
2 2 3
3 3 20

出力例 3

20

このテストケースは小課題 1 の制約を満たします。