题目描述

嘉嘉有一个长度为 $n$ 的数列，初始全部为 $0$，嘉嘉对这个数列进行了 $m$ 次区间加一的操作，称最终得到的序列为 $A$。

她要从中删除不超过 $k$ 条操作，使得数列从 $A$ 变成 $B$。

嘉嘉有一个长度为 $n$ 的数组 $C$。如果对于一个位置 $w$，满足 $B_w \le \dfrac{A_w}{2}$，则这个位置对答案有 $C_w$ 的贡献。

因为嘉嘉十分可爱，所以 ACATM 帮她求出了最大答案。现在他要来考考你。

输入格式

• 第一行三个正整数 $n,m,k$，含义如题面所示。
• 第二行 $n$ 个整数 $C_i$，表示每个位置的贡献。
• 接下来的 $m$ 行，每行两个正整数 $1 \le l \le r \le n$，表示一个区间加一操作。

输出格式

一行一个整数，表示最大答案。

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

10 7 3
794913529 450296950 172761902 781614563 938220829 650645088 307374643 76710749 786303228 736868963
5 9
4 7
5 9
1 2
4 5
2 7
9 9

15 6 1
251922783 841905999 284412472 282267689 976506312 394363952 195030717 242876458 345317806 765692926 641864028 975448345 772558904 68890640 823771941
6 12
15 15
8 10
7 14
2 14
3 5

15 8 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3 14
9 10
4 13
2 11
8 10
2 4
1 10
5 14

15 8 3
989522717 837117765 960476481 128838366 872978869 534821034 14706794 844761293 325663809 555147184 431965315 5307811 34197425 241192392 488824195
1 1
2 2
3 5
6 6
7 7
8 8
9 11
12 14

40

4119182352

3872828751

12

4753416936

数据范围与提示

对于 100% 的数据：

• $1 \le n \le 4 \times 10^4$
• $1 \le m \le 10^5$
• $1 \le k \le \min(5,m)$
• $0 \le C_i \le 10^9$

Subtask：

• Subtask 1（10 pts）：$1 \le n,m \le 25$。
• Subtask 2（10 pts）：$k=1$。
• Subtask 3（10 pts）：$\forall\,1 \le i \le n,\ A_i \le 2$。
• Subtask 4（10 pts）：$k \le 2$。
• Subtask 5（5 pts）：这些区间不交。
• Subtask 6（10 pts）：$1 \le n \le 5 \times 10^3,\ 1 \le m \le 10$。
• Subtask 7（20 pts）：$1 \le n \le 5 \times 10^3$。
• Subtask 8（25 pts）：无特殊限制。