题目描述

考虑一个长度为 $N$ 的序列 $X=(X_1,X_2,\ldots,X_N)$。初始时，$X$ 的所有元素均为零。另给定一个由 $N$ 个非负整数组成的序列 $P=(P_1,P_2,\ldots,P_N)$。

有 $M$ 个按钮。每按一次第 $i$ 个按钮，就会使所有满足 $L_i\le j\le R_i$ 的整数 $j$ 对应的 $X_j$ 增加 $1$。每个按钮都可以按任意次，包括零次。

按按钮的方式必须保证，对于每个 $i=1,2,\ldots,N$，$X_i$ 的最终值都不超过 $K$。

在所有合法的按按钮方式中，求

的最大可能值。

输入格式

输入包含一组或多组测试数据。第一行包含整数 $t$（$1\le t\le 10^5$），表示测试数据组数。随后依次给出 $t$ 组测试数据，每组格式如下。

N M K
P_1 P_2 ... P_N
L_1 R_1
...
L_M R_M

每组测试数据的第一行包含三个整数 $N,M,K$，分别表示序列 $X$ 的长度、按钮数以及 $X$ 中每个元素的上界，满足 $1\le N,M,K\le 2\times 10^5$。

第二行包含 $N$ 个整数 $P_1,P_2,\ldots,P_N$。对于每个 $i$（$1\le i\le N$），整数 $P_i$ 表示 $X_i$ 的权值，满足 $0\le P_i\le 10^7$。

接下来的 $M$ 行每行包含两个整数 $L_j,R_j$（$1\le j\le M$），满足 $1\le L_j\le R_j\le N$，表示第 $j$ 个按钮影响的区间。

所有测试数据的 $N$ 之和、$M$ 之和、$K$ 之和分别不超过 $6\times 10^5$。

输出格式

输出 $t$ 行。对于每组测试数据，单独输出一行，表示所有合法的按按钮方式中 $\sum_{i=1}^{N}P_iX_i$ 的最大可能值。

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

14
35
50

提示

在第一组测试数据中，将第 $2$ 个和第 $3$ 个按钮各按两次，可得到 $X=(0,2,2,2)$。此时加权和为 $3\times 0+1\times 2+4\times 2+2\times 2=14$，这就是最大可能值。