题目描述
小 I 正在打一款回合制 RPG 的最终 boss 战。这一战中,主角和 TA 的 (n−1) 个队友(也就是总共 n 个人)会按照固定的顺序依次行动,目标是对 boss 产生尽可能高的总伤害。
游戏设定中共有 x 种攻击模式,第 i(1≤i≤x) 种攻击模式会对 boss 产生 di 的基础伤害。
在行动过程中可以对 boss 附着异常状态。异常状态共 y 种,同一时刻 boss 不会陷入两种异常状态。当 boss 陷入特定的异常状态时,使用特定的攻击模式会触发暴击,产生更大的伤害。暴击的规则由 m 个三元组 (pj,qj,cj) 给出,表示在附着第 pj(1≤pj≤y) 种异常状态时使用第 qj(1≤qj≤x) 种攻击模式会额外产生 cj 的伤害。
对战开始时,boss 没有陷入任何的异常状态。按照行动顺序,第 i(1≤i≤n) 个人可以进行以下三种行动:
- 使用法术使 boss 陷入第 ai 种异常状态,若 boss 之前陷入了其他异常状态,则之前的异常状态被移除。
- 使用第 bi 种攻击模式对 boss 进行攻击,无论是否触发暴击,在产生伤害之后 boss 的异常状态被移除。
- 摸鱼,即什么都不做,此时 boss 的异常状态被保留。
作为剧情党,小 I 自然是不想自己算最优策略,于是他把问题丢给了你。于是你需要求出 n 次行动内总共能产生最多多少伤害。
输入格式
从标准输入读入数据。
输入的第一行四个整数 n,m,x,y(1≤n,m,x,y≤2×105),分别表示行动次数、暴击规则数、攻击模式种类数和异常状态种类数。
第二行 x 个整数 d1,d2,⋯,dx(1≤di≤109),依次描述每种攻击模式对 boss 产生的基础伤害量。
接下来 n 行第 i 行两个整数 ai,bi(1≤ai≤y,1≤bi≤x),按照行动次序描述第 i 个人的行动。
接下来 m 行第 j 行三个整数 pj,qj,cj(1≤pj≤y,1≤qj≤x,1≤cj≤109),描述第 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。