Type: Default 1000ms 256MiB

硬币

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.

题面描述

Arisa 一共会掷 NN 次硬币,她有一个初始为 00 的计数器。

ii 次掷硬币后,会有两种情况:

  • 如果硬币正面朝上:Arisa 会将计数器的值加一,并获得 XiX_i 元;
  • 如果硬币反面朝上:Arisa 会将计数器重置(值变为 00)。

另外,还有 MM 种特殊奖金:对于第 ii 种奖金,每次计数器显示 CiC_i 的时候,Arisa 会获得 YiY_i 元。

Arisa 想知道她最多可以赚多少钱。

输入格式

第一行两个整数 NNMM

第二行 NN 个整数 X1,X2,,XNX_1,X_2,\dots, X_N

第三至 M+2M+2 行,第 i2i - 2 行两个整数 Ci,YiC_i,Y_i

输出格式

一行一个整数,表示答案。

样例

输入 1

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

输出 1

48

样例 1 解释

11 次硬币正面朝上,计数器值变为 11,获得 22 元;

22 次硬币正面朝上,计数器值变为 22,获得 7+107+10 元;

33 次硬币反面朝上,计数器重置;

44 次硬币正面朝上,计数器值变为 11,获得 88 元;

55 次硬币正面朝上,计数器值变为 22,获得 2+102+10 元;

66 次硬币正面朝上,计数器值变为 33,获得 8+18+1 元。

Arisa 共获得 2+(7+10)+8+(2+10)+(8+1)=482+(7+10)+8+(2+10)+(8+1)=48 元。

输入 2

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

输出 2

5000000000

数据范围

  • 1MN50001 \leq M \leq N \leq 5000
  • 1Xi1091 \leq X_i \leq 10 ^9
  • 1CiN1 \leq C_i \leq N
  • 1Yi1091 \leq Y_i \leq 10^9
  • C1,C2,,CMC_1,C_2,\dots,C_M 互不相同

测试比赛功能

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
8
Start at
2022-9-14 10:45
End at
2022-9-14 12:15
Duration
1.5 hour(s)
Host
Partic.
19