### 问题描述 上个周末，在 $LQ$ 的射击场进行了一场别开生面的射击比赛~ 已知射击场有 $n$ 个靶子，射中每个靶子可以分别得到 $a_1,a_2,...,a_n$ 的分数。**每个靶子最多射击一次！** 但是为了增加比赛的趣味性，现在裁判组设置一个奖励机制： $\bullet$ 比赛一共有 $m$ 种奖励分； $\bullet$ 如果连续射中 $c_i$ 个靶子，可以额外得到 $b_i$ 的加分； $\bullet$ 一旦脱靶，那么连续射中靶数归 $0$。 问：完成 $n$ 次射击以后，最多可以获得多少分。 ### 输入格式 输入第 $1$ 行包含两个正整数 $n$ 和 $m$。 输入第 $2$ 行包含 $n$ 个正整数 $a_i$。 第 $3\sim m+2$ 行每行输入两个正整数 $c_i$ 和 $b_i$。 **题目测试数据保证每个 $c_i$ 都不一样**！ ### 输出格式 输出一行，这一行包含一个整数，表示答案。 ### 样例输入1 ``` 6 3 2 7 1 8 2 8 2 10 3 1 5 5 ``` ### 样例输出1 ``` 48 ``` ### 样例输入2 ``` 3 2 1000000000 1000000000 1000000000 1 1000000000 3 1000000000 ``` ### 样例输出2 ``` 5000000000 ``` ### 说明/提示 对于所有测试数据，$1≤n≤5000，0≤m≤n，1\leq a_i\leq 10^9，1\leq c_i\leq n，1\leq b_i\leq 10^9$。 样例 $1$ 中， 第一次射中靶 $1$，得到 $2$ 分基础分； 第二次射中靶 $2$，得到 $7$ 分基础分，外加 $10$ 分奖励分； 第三次选择脱靶，不得分； 第四次射中靶 $4$，得到 $8$ 分基础分； 第五次射中靶 $5$，得到 $2$ 分基础分，外加 $10$ 分奖励分； 第六次射中靶 $6$，得到 $8$ 分基础分，外加 $1$ 分奖励分。 所以最后的总得分 $ans=2+(7+10)+8+(2+10)+(8+1)=48$。 经过验证，此射击方案是最佳选择。