{"problem":{"name":"[THUPC 2024 决赛] RPG","description":{"content":"小 I 正在打一款回合制 RPG 的最终 boss 战。这一战中，主角和 TA 的 $(n-1)$ 个队友（也就是总共 $n$ 个人）会按照固定的顺序依次行动，目标是对 boss 产生尽可能高的总伤害。 游戏设定中共有 $x$ 种攻击模式，第 $i (1 \\le i \\le x)$ 种攻击模式会对 boss 产生 $d_i$ 的基础伤害。 在行动过程中可以对 boss 附着异常状态。异常状态共","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10542"},"statements":[{"statement_type":"Markdown","content":"小 I 正在打一款回合制 RPG 的最终 boss 战。这一战中，主角和 TA 的 $(n-1)$ 个队友（也就是总共 $n$ 个人）会按照固定的顺序依次行动，目标是对 boss 产生尽可能高的总伤害。\n\n游戏设定中共有 $x$ 种攻击模式，第 $i (1 \\le i \\le x)$ 种攻击模式会对 boss 产生 $d_i$ 的基础伤害。\n\n在行动过程中可以对 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$ 的伤害。\n\n对战开始时，boss 没有陷入任何的异常状态。按照行动顺序，第 $i (1 \\le i \\le n)$ 个人可以进行以下三种行动：\n\n- 使用法术使 boss 陷入第 $a_i$ 种异常状态，若 boss 之前陷入了其他异常状态，则之前的异常状态被移除。\n- 使用第 $b_i$ 种攻击模式对 boss 进行攻击，无论是否触发暴击，在产生伤害之后 **boss 的异常状态被移除**。\n- 摸鱼，即什么都不做，此时 boss 的异常状态被保留。\n\n作为剧情党，小 I 自然是不想自己算最优策略，于是他把问题丢给了你。于是你需要求出 $n$ 次行动内总共能产生最多多少伤害。\n\n## Input\n\n输入的第一行四个整数 $n, m, x, y (1 \\le n, m, x, y \\le 2 \\times 10^5)$，分别表示行动次数、暴击规则数、攻击模式种类数和异常状态种类数。\n\n第二行 $x$ 个整数 $d_1,d_2,\\cdots,d_x (1 \\le d_i \\le 10^9)$，依次描述每种攻击模式对 boss 产生的基础伤害量。\n\n接下来 $n$ 行第 $i$ 行两个整数 $a_i, b_i (1 \\le a_i \\le y, 1 \\le b_i \\le x)$，按照行动次序描述第 $i$ 个人的行动。\n\n接下来 $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\n## Output\n\n输出一行一个整数，表示 $n$ 次行动对 boss 产生的伤害量总和的最大值。\n\n[samples]\n\n## Note\n\n样例中共有两种攻击模式和两种异常状态，其中第一种攻击模式会造成 $10$ 的基础伤害，第二种攻击模式会造成 $1$ 的基础伤害。暴击规则仅有一条：在第二种异常状态下进行第二种攻击会额外造成 $10^9$ 的伤害。\n\n最优的行动策略如下：\n\n- 第一个人使用法术使 boss 陷入第二种异常状态；\n- 第二个人摸鱼，boss 仍然陷入第二种异常状态；\n- 第三个人使用第二种攻击模式，产生 $1$ 的基础伤害和 $10^9$ 的暴击伤害，boss 的异常状态被清除；\n- 第四个人使用第二种攻击模式，产生 $1$ 的基础伤害。\n\n总伤害量为 $1 + 10^9 + 1 = 10^9+2$。\n\n**来源与致谢**\n\n来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。\n\n数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10542","tags":["2024","THUPC"],"sample_group":[["4 1 2 2\n10 1\n2 1\n1 1\n1 2\n2 2\n2 2 1000000000\n","1000000002\n"]],"created_at":"2026-03-03 11:09:25"}}