Xiao L is participating in the annual algorithm competition event, SXCPC!

There are $K$ problems in this year's competition. Xiao L and his teammates have only $n$ minutes to solve them. Xiao L and his teammates do not have good synergy, and they even make the amateur mistake of "thinking about problems that have already been solved" during the competition! Their strategy is: at the $i$-th minute, if the problem with ID $a_i$ is currently in the "unsolved" state, they will solve it.

Xiao L's opponent, Xiao Y, does not want him to solve too many problems, so he bribed the competition organizers. The organizers provided $m$ types of sabotage schemes. The $i$-th scheme consists of setting all problems with IDs in the range $[L_i, R_i]$ to "unsolved" before the $t$-th minute ($1 \leq t \leq n$). Here, $t$ is an arbitrary time point, and exactly one sabotage scheme must be chosen, which can be executed exactly once.

Let $b_i$ be the difficulty of the $i$-th problem (a non-negative integer). Define $C_t$ as the sum of $b_i$ for all problems that remain in the "unsolved" state after the competition ends, given that the sabotage is applied at the $t$-th minute. Xiao Y's happiness value is defined as $(n-t+1) \times C_t$. Please calculate the maximum happiness value Xiao Y can obtain.

Input

The first line contains three positive integers $n, m, K$, representing the competition duration, the number of sabotage schemes, and the number of problems, respectively.

The second line contains $n$ positive integers $a_i$, as described in the problem statement.

The third line contains $K$ positive integers $b_i$, as described in the problem statement.

The next $m$ lines each contain two positive integers $L_i, R_i$, as described in the problem statement.

Output

Output a single integer representing the maximum happiness value that can be obtained.

Examples

Input 1

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

Output 1

36

Constraints

For all data, we have:

• $1 \leq n, m, K \leq 10^6$
• $1 \leq a_i \leq K$
• $0 \leq b_i \leq 10^6$
• $1 \leq L_i \leq R_i \leq K$

Subtasks