Problem Description

Consider a sequence $X=(X_1,X_2,\ldots,X_N)$ of length $N$. Initially, all elements of $X$ are zero. You are also given a sequence $P=(P_1,P_2,\ldots,P_N)$ of $N$ nonnegative integers.

There are $M$ buttons. Pressing the $i$-th button once increases $X_j$ by $1$ for every integer $j$ satisfying $L_i\le j\le R_i$. Each button may be pressed any number of times, including zero.

The buttons must be pressed so that, for every $i=1,2,\ldots,N$, the final value of $X_i$ is at most $K$.

Find the maximum possible value of

among all valid ways of pressing the buttons.

Input Format

The input contains one or more test cases. The first line of the input contains an integer $t$ ($1\le t\le 10^5$), which is the number of test cases. The descriptions of the $t$ test cases follow, each in the following format.

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

The first line of each test case contains three integers $N$, $M$, and $K$, representing the length of the sequence $X$, the number of buttons, and the upper bound for each element of $X$, respectively. They satisfy $1\le N,M,K\le 2\times 10^5$.

The second line contains $N$ integers $P_1,P_2,\ldots,P_N$. For each $i$ ($1\le i\le N$), the integer $P_i$ represents the weight of $X_i$ and satisfies $0\le P_i\le 10^7$.

Each of the following $M$ lines contains two integers $L_j$ and $R_j$ ($1\le j\le M$). They satisfy $1\le L_j\le R_j\le N$ and represent the interval affected by the $j$-th button.

The sum of $N$, $M$, and $K$ over all test cases does not exceed $6\times 10^5$ each.

Output Format

Output $t$ lines. For each test case, output the maximum possible value of $\sum_{i=1}^{N}P_iX_i$ among all valid ways of pressing the buttons, in a separate line.

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

Hint

In the first test case, pressing the second and third buttons twice each results in $X=(0,2,2,2)$. The resulting sum is then $3\times 0+1\times 2+4\times 2+2\times 2=14$, which is the maximum possible value.