时间限制：1秒　　内存限制：256M

---

【题目描述】

　　FJ最近购买了 \(N\) 台挤奶机，编号为 \(1..N（1≤N≤40000）\)，并排成一行。第 \(i\) 台挤奶机每天能够挤 \(m_i(1≤m_i≤100,000)\) 单位的牛奶 。

　　由于机器间距离太近，使得两台相邻的机器不能在同一天使用。FJ可以自由选择不同的机器集合在不同的日子进行挤奶。在 \(D(1≤D≤50,000)\) 天中，每天FJ 对某一台挤奶机进行维护，改变该挤奶机的当天产量。

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

【输入格式】

　　第 1 行：两个整数 \(N\) 和 \(D\)
　　第 2..\(N+1\) 行：每台挤奶机的\(m_i\)
　　第 \(N+2\)..\(N+D+1\) 行：两个整数 \(i\) 和 \(m_i\)，表示每天对机器 \(i\) 进行维护，机器 \(i\) 的产量为 \(c_i\)。

【输出格式】

　　最大产量。

【输入输出样例】

　Input

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

　Output

32

【数据限制】

　　第1天，最优方案为2+4=6 ( 方案1+3+2一样)
　　第2天，最优方案为7+4=11
　　第3天，最优方案为10+3+2=15

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤40000\)，\(1≤m_i, c_i≤100,000\)，\(1≤D≤50,000\)

【来源】

　　Mr.he**