QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 512 MB
[+3]

# 8741. RPG

Statistics

题目描述

小 I 正在打一款回合制 RPG 的最终 boss 战。这一战中,主角和 TA 的 (n1) 个队友(也就是总共 n 个人)会按照固定的顺序依次行动,目标是对 boss 产生尽可能高的总伤害。

游戏设定中共有 x 种攻击模式,第 i(1ix) 种攻击模式会对 boss 产生 di 的基础伤害。

在行动过程中可以对 boss 附着异常状态。异常状态共 y 种,同一时刻 boss 不会陷入两种异常状态。当 boss 陷入特定的异常状态时,使用特定的攻击模式会触发暴击,产生更大的伤害。暴击的规则由 m 个三元组 (pj,qj,cj) 给出,表示在附着第 pj(1pjy) 种异常状态时使用第 qj(1qjx) 种攻击模式会额外产生 cj 的伤害。

对战开始时,boss 没有陷入任何的异常状态。按照行动顺序,第 i(1in) 个人可以进行以下三种行动:

  • 使用法术使 boss 陷入第 ai 种异常状态,若 boss 之前陷入了其他异常状态,则之前的异常状态被移除。
  • 使用第 bi 种攻击模式对 boss 进行攻击,无论是否触发暴击,在产生伤害之后 boss 的异常状态被移除
  • 摸鱼,即什么都不做,此时 boss 的异常状态被保留。

作为剧情党,小 I 自然是不想自己算最优策略,于是他把问题丢给了你。于是你需要求出 n 次行动内总共能产生最多多少伤害。

输入格式

从标准输入读入数据。

输入的第一行四个整数 n,m,x,y(1n,m,x,y2×105),分别表示行动次数、暴击规则数、攻击模式种类数和异常状态种类数。

第二行 x 个整数 d1,d2,,dx(1di109),依次描述每种攻击模式对 boss 产生的基础伤害量。

接下来 n 行第 i 行两个整数 ai,bi(1aiy,1bix),按照行动次序描述第 i 个人的行动。

接下来 m 行第 j 行三个整数 pj,qj,cj(1pjy,1qjx,1cj109),描述第 j 条暴击规则。保证 (pj,qj) 两两不同。

输出格式

输出到标准输出。

输出一行一个整数,表示 n 次行动对 boss 产生的伤害量总和的最大值。

样例

输入

4 1 2 2
10 1
2 1
1 1
1 2
2 2
2 2 1000000000

输出

1000000002

解释

样例中共有两种攻击模式和两种异常状态,其中第一种攻击模式会造成 10 的基础伤害,第二种攻击模式会造成 1 的基础伤害。暴击规则仅有一条:在第二种异常状态下进行第二种攻击会额外造成 109 的伤害。

最优的行动策略如下:

  • 第一个人使用法术使 boss 陷入第二种异常状态;
  • 第二个人摸鱼,boss 仍然陷入第二种异常状态;
  • 第三个人使用第二种攻击模式,产生 1 的基础伤害和 109 的暴击伤害,boss 的异常状态被清除;
  • 第四个人使用第二种攻击模式,产生 1 的基础伤害。

总伤害量为 1+109+1=109+2