问题描述

Takahashi 要抛掷一枚硬币 $N$ 次。他还有一个计数器，初始值为 $0$。

根据第 $i$ 次抛硬币的结果，会出现以下情况：

• 如果是正面：Takahashi 将计数器的值增加 $1$ 并得到 $X_i$ 日元（日本货币）。
• 如果是反面：他将计数器的值重置为 $0$，并且不得到任何钱。

此外，还有 $M$ 种连续奖励。第 $i$ 种连续奖励在计数器显示为 $C_i$ 时每次奖励 $Y_i$ 日元。

找到 Takahashi 可以得到的最多金额。

约束条件

• $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$ 是全部不同的。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入中给出：

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

输出

以整数形式打印 Takahashi 可以得到的最大金额。

示例输入1

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

示例输出1

48

如果按照正面、正面、反面、正面、正面、正面的顺序出现结果，将获得以下金额：

• 在第一次抛硬币时，硬币为正面朝上。将计数器的值从 $0$ 改变为 $1$ 并获得 $2$ 日元。
• 在第二次抛硬币时，硬币为正面朝上。将计数器的值从 $1$ 改变为 $2$ 并获得 $7$ 日元。此外，作为连续奖励还获得 $10$ 日元。
• 在第三次抛硬币时，硬币为反面朝上。将计数器的值从 $2$ 更改为 $0$。
• 在第四次抛硬币时，硬币为正面朝上。将计数器的值从 $0$ 更改为 $1$ 并获得 $8$ 日元。
• 在第五次抛硬币时，硬币为正面朝上。将计数器的值从 $1$ 更改为 $2$ 并获得 $2$ 日元。此外，作为连续奖励还获得 $10$ 日元。
• 在第六次抛硬币时，硬币为正面朝上。将计数器的值从 $2$ 更改为 $3$ 并获得 $8$ 日元。此外，作为连续奖励还获得 $1$ 日元。

在这种情况下，Takahashi 总共获得 $2+(7+10)+0+8+(2+10)+(8+1)=48$ 日元，这是可能的最大金额。
请注意，每当计数器显示为 $C_i$ 时都会授予连续奖励任意次数。
补充一下，如果在所有 $6$ 次抛硬币中都是正面朝上，那么他只能获得 $2+(7+10)+(1+1)+8+(2+5)+8=44$ 日元，这不是最大值。

示例输入2

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

示例输出2

5000000000

请注意，答案可能不适合 $32$ 位整数类型。