A27804.投硬币

时间限制：2000ms
内存限制：256MB

小码君接下来会投掷硬币 $N$ 次。他还有一个计数器，初始值为 0。

根据第 $i$ 次掷硬币的结果：

• 如果是正面：将计数器的值增加 $1$，并获得 $X_i$ 元。
• 如果是反面：将计数器的值重置为 $0$，并且不会得到钱。

另外，还有 $M$ 种额外奖金。
第 $i$ 种奖金会在计数器的值为 $C_i$ 时，每次奖励 $Y_i$ 元。

求小码君能获得的最大金额。

$\large{数据范围}$

• $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$ 互不相等。
• 所有输入数值均为整数。

对于每个测试文件格式如下：

$\tt{N\ M}$
$\tt{X_1\ X_2\ \ldots\ X_N}$
$\tt{C_1\ Y_1}$
$\tt{C_2\ Y_2}$
$\tt{\vdots}$
$\tt{C_M\ Y_M}$

对于每个测试文件输出小码君能够获得的最大金额。

样例 $1$：
若投硬币的结果依次为正，正，反，正，正，正：

• 在第 $1$ 次掷硬币中，为正面。将计数器的值从 $0$ 改为 $1$ ，获得 $2$ 元。
• 在第 $2$ 次抛硬币中，为正面。将计数器的值从 $1$ 改为 $2$ ，得到 $7$ 元。此外，还可以获得 $10$ 元的奖金。
• 在第 $3$ 次抛硬币中，为反面。将计数器的数值从 $2$ 改为 $0$ 。
• 在第 $4$ 次抛硬币中，为正面。将计数器的值从 $0$ 改为 $1$ ，得到 $8$ 元。
• 在第 $5$ 次抛硬币中，为正面。将计数器的值从 $1$ 改为 $2$ ，得到 $2$ 元。此外，还能获得 $10$ 元的额外奖金。
• 在 $6$ 次抛硬币中，为正面。将计数器的值从 $2$ 改为 $3$ ，即可获得 $8$ 元。此外，还能获得 $1$ 元的额外奖励。

在这种情况下，总共获得可以获得 $2+(7+10)+0+8+(2+10)+(8+1)=48$ 元，这是可能获得的最高数额。
请注意，每次计数器显示 $C_i$ 时，都可以获得 $Y_i$ 元奖金。
顺便提一下，如果他在所有掷硬币的 $6$ 中都得到了正面，那么他只能得到 $2+(7+10)+(1+1)+8+(2+5)+8=44$ 元。

样例 $2$：
请注意，答案可能会超出 $32$ 位整数类型。