You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

本题较为卡常，请使用较快的输入输出方式，并开启 O2 优化。

Description

月宫亚由想买 $n$ 个物品，获得物品 $i$ 需要耗费代价 $a_i$。

亚由有 $m$ 次可以在任意时刻进行的操作，每个操作为给定一个正整数二元组 $(r_i,w_i)$，并将某一个 $j\in[1,r_i]$，执行 $a_j\gets a_j-w_i$。每个 $\boldsymbol{a_j}$ 最多被修改一次。

现在亚由需要获得恰好 $k$ 个物品，最小化耗费的代价。

Format

Input

第一行两个整数 $n, m$。

接下来一行 $n$ 个整数 $a_i$。

接下来 $m$ 行每行两个整数 $r_i , w_i$。

接下来一行一个整数 $k$。

Output

一行一个整数。

Samples

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

12

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

-5

Limitation

对于 $10\%$ 的数据，$1\le n, m ≤ 8$。

对于 $30\%$ 的数据，$1\le n, m ≤ 500$。

对于 $60\%$ 的数据，$1\le n, m ≤ 2000$。

对于 $100\%$ 的数据，$1 ≤ n ≤ 10^5$，$1 ≤ m ≤ 2 × 10^5$，$1\le a_i , w_i ≤ 10^9$，$1\le r_i,k ≤ n$。