掷硬币与连胜奖励

题目描述

Takahashi 将掷 $N$ 次硬币。 他还有一个计数器,初始值为 $0$。

根据第 $i$ 次掷硬币的结果,会发生以下情况:

如果正面朝上:Takahashi 将计数器的值加 $1$,并获得 $X_i$ 日元(日本货币)。

如果反面朝上:他将计数器的值重置为 $0$,且不获得钱。

此外,还有 $M$ 种连胜奖励。第 $i$ 种连胜奖励会在计数器每次显示 $C_i$ 时给予 $Y_i$ 日元。

求 Takahashi 最多能获得多少钱。

输入格式

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

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

输出格式

输出 Takahashi 最多能获得的钱数,以整数形式。

样例

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

48

如果依次得到正、正、反、正、正、正,则会获得以下金额。

第 $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$ 日元。

这种情况下,Takahashi 一共获得 $2+(7+10)+0+8+(2+10)+(8+1)=48$ 日元,这是最大值。

注意,连胜奖励在计数器每次显示 $C_i$ 时都会被发放,次数没有限制。

顺带一提,如果 $6$ 次硬币全部正面朝上,则只获得 $2+(7+10)+(1+1)+8+(2+5)+8=44$ 日元,并不是最大值。

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

5000000000

注意,答案可能超出 $32$ 位整数类型的范围。

数据范围

• $1 \le M \le N \le 5000$
• $1 \le X_i \le 10^9$
• $1 \le C_i \le N$
• $1 \le Y_i \le 10^9$
• $C_1,C_2,\ldots,C_M$ 两两不同
• 输入均为整数