問題文

高橋くんは 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

入力例 1

4 3 2
5 6 3 7
1 1
2 3
3 4

出力例 1

8

入力例 2

5 5 5
8 6 9 1 20
1 2
3 4
5 5
4 5
3 5

出力例 2

-1