P17550 [JAG 2026 Summer Camp #2] Buttons

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 $$ \sum_{i=1}^{N}P_iX_i $$ among all valid ways of pressing the buttons.

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. ```text 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 $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.

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.