题目描述

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

游戏设定中共有 $x$ 种攻击模式，第 $i (1 \le i \le x)$ 种攻击模式会对 boss 产生 $d_i$ 的基础伤害。

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

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

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

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

输入格式

输入的第一行四个整数 $n, m, x, y (1 \le n, m, x, y \le 2 \times 10^5)$，分别表示行动次数、暴击规则数、攻击模式种类数和异常状态种类数。

第二行 $x$ 个整数 $d_1,d_2,\cdots,d_x (1 \le d_i \le 10^9)$，依次描述每种攻击模式对 boss 产生的基础伤害量。

接下来 $n$ 行第 $i$ 行两个整数 $a_i, b_i (1 \le a_i \le y, 1 \le b_i \le x)$，按照行动次序描述第 $i$ 个人的行动。

接下来 $m$ 行第 $j$ 行三个整数 $p_j, q_j, c_j (1 \le p_j \le y, 1 \le q_j \le x, 1 \le c_j \le 10^9)$，描述第 $j$ 条暴击规则。保证 $(p_j, q_j)$ 两两不同。

输出格式

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

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

1000000002

提示

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

最优的行动策略如下：

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

总伤害量为 $1 + 10^9 + 1 = 10^9+2$。

来源与致谢

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 https://thusaac.com/public