D. Coffee
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The girls of HTT like drinking tea. But one day, they wanted a change and decided to try coffee in the next $$$n$$$ days.

Now Mugi, who always provides food and drinks for HTT, will go to the shop to buy some coffee. She learns that the price of coffee on day $$$i$$$ is $$$a_i$$$ . Now she has $$$m$$$ coupons. The $$$i$$$ th coupon can be used before day $$$r_i$$$ (it can also be used on day $$$r_i$$$) and can reduce the price of coffee on that day by $$$w_i$$$ . $$$\textbf{Notice that the price can be a negative number after using the coupon.}$$$ Each coupon can be used only once, and Mugi cannot use more than one coupon per day.

Since the girls of HTT still need to drink tea, Mugi decided to choose $$$\textbf{exactly}$$$ $$$k$$$ days to buy coffee. Now she wants to know the minimum money she will spend (or the maximum money she can get) to choose exactly $$$k$$$ days to buy coffee.

Input

The first line contains two integers $$$n,m\ (1 \le n \le 10^5, 1 \le m \le 2 \times 10^5)$$$ - the number of days and the number of coupons.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n(1 \le a_i \le 10^9)$$$ , and $$$a_i$$$ denoting the price of coffee on day $$$i$$$ .

Next $$$m$$$ lines, each line contains two integers $$$r_i,w_i(1 \le r_i \le n,1 \le w_i \le 10^9)$$$ , denoting that the $$$i$$$ th coupon can be used before day $$$r_i$$$ and can reduce the price by $$$w_i$$$ .

Next line contains an integer $$$k(1 \le k \le n)$$$ , denoting the number of days that Mugi will buy coffee.

Output

One integer - the minimum money Mugi will spend to buy coffee. Notice that the answer can be a negative integer.

Examples
Input
5 2
1 2 3 4 5
3 1
4 2
5
Output
12
Input
7 3
4 3 1 10 3 8 6
4 9
3 8
4 5
5
Output
-5
Note

In the first example, Mugi can use coupon $$$1$$$ on day $$$1$$$ and use coupon $$$2$$$ on day $$$2$$$ to spend $$$0+0+3+4+5=12$$$.

In the second example, Mugi can use coupon $$$1$$$ on day $$$2$$$, coupon $$$2$$$ on day $$$3$$$ and coupon $$$3$$$ on day $$$1$$$. Then she can choose to buy coffee on day $$$1,2,3,5,7$$$ and spend $$$(-1)+(-6)+(-7)+3+6=-5$$$ .