Description

Little $\zeta$ fell into a deep sleep when he couldn't come up with a Problem A of the school mock competition. He dreamed of this problem:

There are two sequences $a,b$ with lengths of $n$. For every $1 \le i \le n$, given the value of $a_i$, The initial value of $b_i$ is $0$. You need to execute the following commands $m$ times:

• l r v: let $v'=v(1-\max_{i=l}^r|b_i|)$. Then for every $l \le i \le r$, $b_i \leftarrow b_i+v'$.

After $m$ executions, you need to output $\sum_{i=1}^na_ib_i$.

He found this problem very interesting, so he downloaded the data package and viewed it. However, due to the wake-up alarm on 6 o'clock, he forgot the value of $v$ and the relative order of the commands. But he knew that the $v$ of each command satisfies $v\in\{-1,1\}$.

He decided to find a way to restore the data of this problem and make appropriate modifications to maximize the answer. The modification is about the arguments of the commands in the problem. He allows himself to perform up to $k$ operations as follows:

• Select $1 \le i \le m$ and apply one of the four operations: $l_i \leftarrow l_i-1$, $l_i \leftarrow l_i+1$, $r_i \leftarrow r_i-1$, $r_i \leftarrow r_i+1$, where $l_i$ and $r_i$ denotes the parameters $l$ and $r$ in the $i$-th command. After that, $1 \le l_i \le r_i \le n$ must be satisfied.

Find the maximum possible output of that problem after all the modifications.

For your convenience in completing this task, little $\zeta$ kindly tells you a very useful property: All given intervals do not strictly contain each other before restoration (i.e. there is no $1 \le i,j \le m$ such that $l_i<l_j \le r_j<r_i$). You do not need to keep it during the modification.

Input Format

The first line contains three integers $n,m,k$, which denote the sequence length, the number of commands, and the number of modifications respectively.

The second line contains $n$ integers, where the $i$-th integer is $a_i$.

On the next $m$ lines, the $i$-th line contains two integers $l_i, r_i$, which denotes the parameters of the $i$-th command.

Output Format

A single integer which denotes the maximum output of that problem.

5 2 2
1 2 -3 -4 5
1 1
2 3

8

5 2 3
1 2 -3 -4 5
1 1
2 3

10

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

38

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

40

10 4 1000
2 2 -3 -4 -5 1 2 -10 -9 -5
2 3
2 5
1 2
6 7

43

Hint

Sample Description #1

• Move the interval $[2,3]$ to $[3,4]$, which costs $2$ modifications;
• Execute the commands $(3,4, -1),(1,1,1)$, and the maximum output is $8$.

Sample Description #3

• Move the interval $[2,5]$ to $[3,5]$, which costs $1$ modifications.
• Move the interval $[6,7]$ to $[7,10]$, which costs $4$ modifications.
• Execute the commands $(3,5, -1),(2,3,1),(1,2,1),(7,10,-1)$, and the maximum output is $38$.

Constraints

This problem uses subtasks.

*: Subtask $1$: Uses the sum instead of the minimum score. Each test cases is worth $5$ points. $5$ points for $k=0$. $10$ points for $k=1$.

For all test cases, it is guaranteed that $1 \le n \le 1000$, $1 \le m \le 100$, $0 \le k \le 1000$，$0 \le |a_i| \le 10^6$.

For any $1 \le i \le m$, it is guaranteed that $1 \le l_i \le r_i \le n$. There is no $1 \le i,j \le m$ such that $l_i<l_j\le r_j<r_i$.