P10542 [THUPC 2024 Finals] RPG

Xiao I is fighting the final boss in a turn-based RPG. In this battle, the main character and their $(n-1)$ teammates (that is, $n$ people in total) will act one by one in a fixed order, aiming to deal as much total damage to the boss as possible. There are $x$ types of attack patterns in the game. The $i$-th $(1 \le i \le x)$ attack pattern deals base damage $d_i$ to the boss. During actions, you can apply status effects to the boss. There are $y$ types of status effects, and at any moment the boss cannot be affected by two status effects at the same time. When the boss is under a specific status effect, using a specific attack pattern will trigger a critical hit and deal more damage. The critical hit rules are given by $m$ triples $(p_j, q_j, c_j)$, meaning that when status effect type $p_j (1 \le p_j \le y)$ is applied, using attack pattern type $q_j (1 \le q_j \le x)$ will deal an **additional** $c_j$ damage. At the start of the battle, the boss has no status effect. In order of actions, the $i$-th $(1 \le i \le n)$ person can take one of the following three actions: - Use a spell to make the boss enter status effect type $a_i$. If the boss previously had another status effect, the previous status effect is removed. - Use attack pattern type $b_i$ to attack the boss. Regardless of whether a critical hit is triggered, after dealing damage, **the boss’s status effect is removed**. - Slack off, i.e., do nothing. In this case, the boss’s status effect is kept. As a story-focused player, Xiao I naturally does not want to calculate the optimal strategy by hand, so he throws the problem to you. You need to find the maximum total damage that can be dealt within the $n$ actions.

The first line contains four integers $n, m, x, y (1 \le n, m, x, y \le 2 \times 10^5)$, representing the number of actions, the number of critical hit rules, the number of attack pattern types, and the number of status effect types. The second line contains $x$ integers $d_1,d_2,\cdots,d_x (1 \le d_i \le 10^9)$, describing the base damage dealt by each attack pattern to the boss. The next $n$ lines each contain two integers. Line $i$ contains $a_i, b_i (1 \le a_i \le y, 1 \le b_i \le x)$, describing the options for the $i$-th person’s action in order. The next $m$ lines each contain three integers. Line $j$ contains $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)$, describing the $j$-th critical hit rule. It is guaranteed that all $(p_j, q_j)$ pairs are distinct.

Output one integer in one line, representing the maximum possible total damage dealt to the boss over the $n$ actions.

In the sample, there are two attack patterns and two status effects. The first attack pattern deals base damage $10$, and the second attack pattern deals base damage $1$. There is only one critical hit rule: under the second status effect, using the second attack pattern deals an additional $10^9$ damage. The optimal strategy is as follows: - The first person uses a spell to make the boss enter the second status effect. - The second person slacks off, and the boss remains under the second status effect. - The third person uses the second attack pattern, dealing base damage $1$ and critical hit damage $10^9$, and the boss’s status effect is cleared. - The fourth person uses the second attack pattern, dealing base damage $1$. The total damage is $1 + 10^9 + 1 = 10^9+2$. **Source and Acknowledgements** From the finals of THUPC2024 (Tsinghua University Student Programming Contest and Collegiate Invitational, 2024). Thanks to THUSAA for providing this problem. For testdata, statement, reference solution, editorial, etc., please refer to the official THUPC repository: . Translated by ChatGPT 5