AT_oupc2023_day1_h Wonderful Stage

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 $ とします。

入力は以下の形式で標準入力から与えられます。 > $ X $ $ M $ $ K $ $ S_1 $ $ S_2 $ $ \dots $ $ S_M $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ $ \vdots $ $ a_K $ $ b_K $ $ c_K $

スコアをちょうど $ X $ にできるならば、達成する必要のある難易度の最大値としてあり得る最小値を $ 1 $ 行で出力してください。スコアをちょうど $ X $ にできない場合は `-1` を出力してください。

### 小課題 1. ( $ 1 $ 点) $ a_j=b_j $ 2. ( $ 99 $ 点) 追加の制約はない ### Sample Explanation 1 $ 4 $ 番目以外のリズムアイコンをタップするのが最適です。 このテストケースは小課題 1 の制約を満たしません。 ### Sample Explanation 2 スコアをちょうど $ 9 $ にすることはできません。 このテストケースは小課題 1 の制約を満たしません。 ### Sample Explanation 3 このテストケースは小課題 1 の制約を満たします。 ### Constraints - $ 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} $ - 入力はすべて整数