/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
高橋君が N 回コイントスを行います。 また、高橋君はカウンタを持っており、最初カウンタの数値は 0 です。
i 回目のコイントスで表裏のどちらが出たかによって、次のことが起こります。
- 表が出たとき：高橋君はカウンタの数値を 1 増やし、X_i 円もらう。
- 裏が出たとき：高橋君はカウンタの数値を 0 に戻す。お金をもらうことは出来ない。
また、M 種類の連続ボーナスがあり、i 種類目の連続ボーナスではカウンタの数値が C_i になるたびに Y_i 円もらうことができます。
高橋君は最大で何円もらうことができるかを求めてください。
制約
- 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
出力
高橋君がもらうことのできる金額の最大値を整数で出力せよ。
入力例 1
6 3 2 7 1 8 2 8 2 10 3 1 5 5
出力例 1
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 円もらう。
このとき高橋君は合計で 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 bit 整数型に収まらないこともあることに注意してください。
Score : 400 points
Problem Statement
Takahashi will toss a coin N times. He also has a counter, which initially shows 0.
Depending on the result of the i-th coin toss, the following happens:
- If it heads: Takahashi increases the counter's value by 1 and receives X_i yen (Japanese currency).
- If it tails: he resets the counter's value to 0, without receiving money.
Additionally, there are M kinds of streak bonuses. The i-th kind of streak bonus awards Y_i yen each time the counter shows C_i.
Find the maximum amount of money that Takahashi can receive.
Constraints
- 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 are all different.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M X_1 X_2 \ldots X_N C_1 Y_1 C_2 Y_2 \vdots C_M Y_M
Output
Print the maximum amount of money that Takahashi can receive, as an integer.
Sample Input 1
6 3 2 7 1 8 2 8 2 10 3 1 5 5
Sample Output 1
48
If he gets head, head, tail, head, head, head, in this order, the following amounts of money are awarded.
- In the 1-st coin toss, the coin heads. Change the counter's value from 0 to 1 and receive 2 yen.
- In the 2-nd coin toss, the coin heads. Change the counter's value from 1 to 2 and receive 7 yen. Additionally, get 10 yen as a streak bonus.
- In the 3-rd coin toss, the coin tails. Change the counter's value from 2 to 0.
- In the 4-th coin toss, the coin heads. Change the counter's value from 0 to 1 and receive 8 yen.
- In the 5-th coin toss, the coin heads. Change the counter's value from 1 to 2 and receive 2 yen. Additionally, get 10 yen as a streak bonus.
- In the 6-th coin toss, the coin heads. Change the counter's value from 2 to 3 and receive 8 yen. Additionally, get 1 yen as a streak bonus.
In this case, Takahashi receives 2+(7+10)+0+8+(2+10)+(8+1)=48 yen in total, which is the maximum possible.
Note that streak bonuses are awarded any number of times each time the counter shows C_i.
As a side note, if he gets head in all 6 coin tosses, he only receives 2+(7+10)+(1+1)+8+(2+5)+8=44 yen, which is not the maximum.
Sample Input 2
3 2 1000000000 1000000000 1000000000 1 1000000000 3 1000000000
Sample Output 2
5000000000
Note that the answer may not fit into a 32-bit integer type.