最高分数: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