Problem E
Economic Inequality

There is an event involving $N$ banks and $M$ stakeholders, where Bob is stakeholder 1. The banks are giving money to the stakeholders, where bank $i$ needs to give out a total of $A_ i$ dollars, and each bank can give each person at most $K$ dollars, to mitigate blatant favouritism. The banks can only give an integer number of dollars to each person, and bank $i$ must give out all $A_ i$ dollars in this event. Additionally, person $i$ starts with $B_ i$ dollars, but can only have at most $C_ i$ dollars after receiving money from the banks, as a measure to reduce collusion.

However, Bob has blackmail material on all of the banks, and thus he has the power to decide how much each bank gives each person. He has a nasty and greedy personality, so he wants to be as rich as possible compared to the other $M - 1$ people. In particular, after the event, let $X$ be the amount of money (in dollars) that Bob (stakeholder 1) has, and $Y$ be the maximum amount of money (in dollars), that any of the stakeholders $2, 3, \dots , M$ has. Then Bob wants to maximise $X - Y$ (though it can be negative). Help Bob determine the maximum possible value of $X - Y$.

Input

The first line of input contains an two integers $N, M, K$ $(1 \leq N\leq 10^5, 2 \leq M \leq 10^5, 1 \leq K \leq 10^{8})$, the number of banks, number of stakeholders, and the maximum amount of money (in dollars) that each bank can give each stakeholder.

The next line contains a $N$ space-separated integers $A_1, A_2, \dots , A_ N$ $(0 \leq A_ i \leq 10^{12})$, the amount of money (in dollars) each bank needs to give out.

The next $M$ lines each contain two space-separated integers, where the $i$-th line contains $B_ i, C_ i$ $(0 \leq B_ i \leq C_ i \leq 10^{13})$, the amount of money (in dollars) stakeholder $i$ starts with and the maximum amount of money (in dollars) he can have after the event.

Additionally, it is guaranteed that the banks will be able to give out all the money for the input data provided.

Output

Output a single integer, the maximum possible value of $X - Y$ as described above.

4 4 3
7 5 3 2
2 8
1 3
5 15
3 12

-1

5 5 5
13 7 9 21 5
15 32
1 5
10 30
2 12
15 29

7