← 返回题目列表

AtCoder · pakencamp_2018_day3_g

G. 失业危机

中文机器翻译题面 查看原题

配点: 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