#D. 小容玩arcaea

    Type: Default 8000ms 512MiB

小容玩arcaea

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

小容玩Arcaea

题目描述

小容正在玩Arcaea

她会点击 NN 次,每次只有击中和未击中两种结果,并且击中会使连击数 +1+1 (连击数初始为 00 )。

对于第 ii 次点击:

  • 如果击中,小容会获取 AiA_{i} 分,连击数 +1+1
  • 如果未击中,连击数清零,她不会得分。

另外,有 MM 种连击得分。对于第 ii 种连击得分,每当连击 BiB_{i} 次时,小容会得到 CiC_{i} 分。

输出小容的最大可能得分。

输入格式

第一行有两个正整数 N,MN,M ,表示点击次数和连击得分种类数。

第二行有 NN 个正整数 A1,A2,,ANA_1,A_2,\cdots,A_N ,表示当第 ii 次点击击中时,得到 AiA_i 分。

接下来第 3M+23\sim M+2 行,每行有两个正整数 Bi,CiB_i,C_i ,表示一种连击得分。

输出格式

输出小容的最大可能得分。

样例 #1

样例输入 #1

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

样例输出 #1

48

样例 #2

样例输入 #2

3 2
10 10 10
1 10
3 10

样例输出 #2

50

提示

数据范围

对于 30%30\% 的数据: N20N\le20

对于 50%50\% 的数据: N500N\le500

对于 100%100\% 的数据: 1M,BiN50001\le M,B_i\le N\le50001Ai,Ci1091\le A_i,C_i\le10^9

样例解释#1

当小容击中第 1,2,4,5,61,2,4,5,6 次点击时,她获得的分数最大,为 2+(7+10)+0+8+(2+10)+(8+1)=482+(7+10)+0+8+(2+10)+(8+1)=48 分,但如果她全部击中,她只能获得 2+(7+10)+(1+1)+8+(2+5)+8=442+(7+10)+(1+1)+8+(2+5)+8=44 分。