配点: 100 点
問題文
高桥君是 N 天里,
您将收到M 家庭作业。这几天之一
您必须至少提交 K 份家庭作业。如果不这样做,你将留级。
第
1 \leq i \leq M 个作业分发日期是 S_i 截止日期是
您可以在 E_i 。S_i 以降 E_i (包括两个截止日期之日)之前提交作业。
另外,每个日期都有“那天你不想做的事情”。i 那天我不想做的是 X_i 。
高桥君可以选择每天做一项作业或不做作业。您一天不能完成两项以上的家庭作业。
此时,K 当高桥做作业当天同时做超过 10 份作业时,将“不想做”的总数最小化,输出“不想做”的总数。
然而,无论你如何尝试,都要做好功课。 如果您不能做的事情超过 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 \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 点]
- 没有其他限制。
入力例 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