← 返回题目列表

AtCoder · s8pc_5_f

F. 午餐菜单

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

最高分数:1000 点

问题陈述

有 N 食品,编号方便 1 通过 N。的 美味 食品 i 正是 a_i.
square1001 将有 Q 午餐。 i第次午餐,他会在数字之间的食物中选择最美味的食物(美味程度最高的食物) l_i 和 r_i (含)。如果没有这些食物,他这次就不会吃午饭了。

你是魔鬼,你可以抹去 M 午餐菜单及其菜单中的食物将不再能够选择。您的目标是尽量减少 square1001 选择的食物的总美味。
计算选择的食物square1001的总美味度的最小值。

输入

输入由标准输入按以下格式给出:

N M Q
a_1 \ a_2 \ a_3 \ \cdots \ a_N
l_1 \ r_1
l_2 \ r_2
l_3 \ r_3
 :  :
l_Q \ r_Q

输出

在一行中打印 square1001 选择的食物总美味度的最小值。


限制。

  • N 是介于 1 和 50 (含)。
  • M 是介于 0 和 N (含)。
  • Q 是介于 1 和 50 (含)。
  • a_i \ (1 \leq i \leq N) 是介于 1 和 1 \ 000 \ 000 \ 000 (含)。
  • l_i, r_i 是整数,其中包含 1 \leq l_i \leq r_i \leq N.

子任务

子任务 1 [60 点]

  • N \leq 15.
  • Q = 1.

子任务 2 [60 点]

  • N \leq 15.

子任务 3 [250 点]

  • a_i = 1 对于所有人 i \ (1 \leq i \leq N).

子任务 4 [630 点]

  • 没有额外的限制。

示例输入 1

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

示例输出 1

27

如果您删除食物 2 和 3,最大美味是 4, 3, 8, 4, 8 按顺序。
总的美味是 27.


示例输入 2

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

示例输出 2

21

示例输入 3

8 5 3
1 1 1 1 1 1 1 1
2 5
1 3
6 8

示例输出 3

1