AT_pakencamp_2018_day3_g 落単の危機

[problemUrl]: https://atcoder.jp/contests/pakencamp-2018-day3/tasks/pakencamp_2018_day3_g 高橋くんは $ N $ 日間の間に、$ M $ 個の宿題を受けとります。そのうち $ K $ 個以上の宿題を提出する必要があります。しないと留年です。 $ 1\ \leq\ i\ \leq\ M $ 番目の宿題の配布日は $ S_i $ で、締め切り日は $ E_i $ です。$ S_i $ 以降 $ E_i $ までの日 (両方の期限の当日も含む) にその宿題をすると提出できます。 また、各日付には「その日のやりたくなさ」があります。$ i $ 日目のやりたくなさは $ X_i $ です。 高橋くんは各日において、「宿題をどれか一つする」または「宿題をしない」を選べます。一日に二つ以上の宿題はできません。 このとき、$ K $ 個以上の宿題をやりつつ、高橋君が宿題をやった日の「やりたくなさ」の合計を最小化するときの、「やりたくなさ」の合計を出力してください。 ただし、どうやっても宿題を $ K $ 個以上行うことができない場合、$ -1 $ を出力してください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ K $ $ X_1 $ $ X_2 $ $ X_3 $ ... $ X_N $ $ S_1 $ $ E_1 $ $ S_2 $ $ E_2 $ $ S_3 $ $ E_3 $ ... $ S_M $ $ E_M $

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 1000 $ - $ 1\ \leq\ K\ \leq\ M\ \leq\ 1000 $ - $ 1\ \leq\ S_i\ \leq\ E_i\ \leq\ N $ - $ 1\ \leq\ X_i\ \leq\ 10^{9} $ - 入力はすべて整数 ### 小課題 小課題 $ 1 $ \[$ 12 $ 点\] 入力は以下の条件を満たす。 - $ N\ \leq\ 6 $ - $ K\ \leq\ 6 $ 小課題 $ 2 $ \[$ 18 $ 点\] 入力は以下の条件を満たす。 - $ N\ \leq\ 15 $ - $ M\ \leq\ 80 $ 小課題 $ 3 $ \[$ 30 $ 点\] 入力は以下の条件を満たす。 - $ S_i\ =\ 1 $ ($ 1\ \leq\ i\ \leq\ M $) 小課題 $ 4 $ \[$ 24 $ 点\] 入力は以下の条件を満たす。 - $ N\ \leq\ 80 $ - $ M\ \leq\ 80 $ 小課題 $ 5 $ \[$ 16 $ 点\] - 追加の制約はない。