题目描述

FarmerJohn 最近购买了 $N\ (1≤ N ≤40000)$ 台挤奶机，编号为 $1 ...N$，并排成一行。

第 $i$ 台挤奶机每天能够挤 $M_i$ 单位的牛奶 $(1≤M_i≤100000)$。由于机器间距离太近，使得两台相邻的机器不能在同一天使用。

FarmerJohn 可以自由选择不同的机器集合在不同的日子进行挤奶。在 $D\ (1≤ D ≤50000)$天中，每天 FarmerJohn对某一台挤奶机进行维护，改变该挤奶机的产量。

FarmerJohn希望设计一个挤奶方案，使得挤奶机能够在 $D$ 天后获取最多的牛奶。

输入格式

第 $1$ 行：两个整数 $N$ 和 $D$。

第 $2..N+1$ 行：每台挤奶机的 $M_i$。

第 $N+2..N+D+1$ 行：两个整数 $i$ 和 $m$，表示每天对机器 $i$ 进行维护，机器 $i$ 的产量为 $m$。

输出格式

最大产量。

5 3
1
2
3
4
5
5 2
2 7
1 10

32

• 第 $1$ 天，最优方案为 $2 + 4=6$（方案 $1 + 3 + 2$ 一样）。
• 第 $2$ 天，最优方案为 $7 + 4=11$。
• 第 $3$ 天，最优方案为 $10 + 3 + 2=15$。