题目描述

高橋君が $N$ 回コイントスを行います。 また、高橋君はカウンタを持っており、最初カウンタの数値は $0$ です。

$i$ 回目のコイントスで表裏のどちらが出たかによって、次のことが起こります。

• 表が出たとき：高橋君はカウンタの数値を $1$ 増やし、$X_i$ 円もらう。
• 裏が出たとき：高橋君はカウンタの数値を $0$ に戻す。お金をもらうことは出来ない。

また、$M$ 種類の連続ボーナスがあり、$i$ 種類目の連続ボーナスではカウンタの数値が $C_i$ になるたびに $Y_i$ 円もらうことができます。

高橋君は最大で何円もらうことができるかを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

高橋君がもらうことのできる金額の最大値を整数で出力せよ。

题目大意

高桥会掷 $N$ 次硬币，他还有一个计数器，初始示数为0。
对于第 $i$ 次掷硬币的结果，高桥会做出如下行为：

• 如果此次硬币为正面，高桥会将计数器 +1，并且获取 $X_{i}$ 元。
• 如果此次硬币为反面，他会将计数器清零，不收到钱。
  另外，有 $M$ 种额外连胜奖励。对于第 $i$ 种连胜奖励，每当计数器示数为 $C_{i}$ 时，奖励 $Y_{i}$ 元。
  输出高桥的最大收益。

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

48

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

5000000000

提示

制約

• $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$ はすべて異なる。
• 入力はすべて整数

Sample Explanation 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$ になるたびに何度でももらえることに注意してください。 ちなみに、$6$ 回のコイントスで全部表が出た時は $2+(7+10)+(1+1)+8+(2+5)+8=44$ 円しかもらうことが出来ず、この時は最大ではありません。

Sample Explanation 2

答えが $32$ bit 整数型に収まらないこともあることに注意してください。