题目描述

小明在玩一个抛硬币游戏，他会掷 $N$ 次硬币，他还有一个计数器，初始示数为0。
对于第 $i$ 次掷硬币的结果，小明会做出如下行为：

• 如果此次硬币为正面，小明会将计数器 +1，并且获取 $X_{i}$ 元。
• 如果此次硬币为反面，他会将计数器清零，不收到钱。

另外，这个游戏有 $M$ 种额外连胜奖励。对于第 $i$ 种连胜奖励，每当计数器示数为 $C_{i}$ 时，奖励 $Y_{i}$ 元。现在问游戏结束后，小明的最大收益是多少。

输入格式

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

第二行输入 $n$ 个整数 $x_1,x_2,...,x_n$ 。

接下来 $m$ 行，每行输入两个整数 $c_i,y_i$ 。

输出格式

输出游戏结束后小明获得的最大收益。

样例 #1

样例输入 #1

6 3
2 7 1 8 2 8
2 10
3 1
5 5

样例输出 #1

48

如果小明投到的顺序是正，正，反，正，正，正，他能获得的收益如下：

• 第一次，投到正面，获得 $2$ 元，计数器变为 $1$ 。
• 第二次，投到正面，获得 $7$ 元，计数器变为 $2$ ，此时可以获得连击奖励，获得 $10$ 元 。
• 第三次，投到反面，无收益，计数器归零。
• 第四次，投到正面，获得 $8$ 元，计数器变为 $1$ 。
• 第五次，投到正面，获得 $2$ 元，计数器变为 $2$ ，此时可以获得连击奖励，获得 $10$ 元 。
• 第六次，投到正面，获得 $8$ 元，计数器变为 $3$ ，此时可以获得连击奖励，获得 $1$ 元 。

最终收益： $2+(7+10)+0+8+(2+10)+(8+1)=48$ ，这个是最大收益。

样例 #2

样例输入 #2

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

样例输出 #2

5000000000

注意最大收益有可能超过 $int$ 的范围。

提示

对于 $100\%$ 的数据：

• $1\leq\ M\leq\ N\leq\ 5000$
• $1\leq\ X_i\leq\ 10^9$
• $1\leq\ C_i\leq\ N$
• $1\leq\ Y_i\leq\ 10^9$
• $C_1,C_2,\ldots,C_M$ 互不相等。
• 所有的输入都是整数。