P16701 [MCO 2026] Creating Combos

Dragon Evirir is playing a video game, and it wants to maximize the total damage by casting skills continuously. Evirir can use $N$ different skills, numbered $0, 1, \ldots, N - 1$. For each skill $i$, its color is $C_i$ and its damage is $D_i$. There are $M$ skill links in total, and each link is a pair of skills $(U_i, V_i)$, where $0 \le i \le M - 1$. A combo is a skill sequence of length $l \ge 1$, $s_0, s_1, \ldots, s_{l - 1}$, such that for all $0 \le i < l - 1$, $(s_i, s_{i+1})$ is one of the $M$ skill links. The problem guarantees that the skill links in the input do not form a cycle. In other words, it is impossible to build a combo that uses the same skill twice. The total power of the combo is computed as follows. Let there be a multiplier $B$, initially $B = 1$. For $i = 0, 1, \ldots, l - 1$, do the following in order: - If $i = 0$, do nothing. - Otherwise: - If skills $s_i$ and $s_{i - 1}$ have the same color, multiply $B$ by $2$. - If skills $s_i$ and $s_{i - 1}$ have different colors, set $B$ to $1$. - Then, the power of skill $s_i$ is $D_{s_i} \times B$. The total power of the combo is the sum of the powers of all cast skills. For example, suppose a combo contains the following skills in order: $(3,7)$, $(2,5)$, $(4,7)$, $(1,7)$, $(5,7)$, $(6,7)$, $(3,6)$, where $(x, y)$ means a skill with damage $x$ and color $y$. The computation is as follows: | | $s_0$ | $s_1$ | $s_2$ | $s_3$ | $s_4$ | $s_5$ | $s_6$ | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | Color $C_{s_i}$ | $7$ | $5$ | $7$ | $7$ | $7$ | $7$ | $6$ | | Damage $D_{s_i}$ | $3$ | $2$ | $4$ | $1$ | $5$ | $6$ | $3$ | | Multiplier $B$ | $1$ | $1$ | $1$ | $2$ | $4$ | $8$ | $1$ | | Power | $3 \times 1 = 3$ | $2 \times 1 = 2$ | $4 \times 1 = 4$ | $1 \times 2 = 2$ | $5 \times 4 = 20$ | $6 \times 8 = 48$ | $3 \times 1 = 3$ | Therefore, the total power of this combo is $3 + 2 + 4 + 2 + 20 + 48 + 3 = 82$. Clearly, Evirir wants to cast a combo with the maximum total power. To do this, it installed a cheat that can change the color of any skill to a fixed color $T$. Evirir can use this cheat at most $K$ times (that is, it can modify the colors of at most $K$ skills). Find the maximum total power Evirir can achieve. If the maximum total power is strictly greater than $10^9$, output $-1$.

The first line contains four integers $N$, $M$, $K$, and $T$, separated by spaces. Then there are $N$ lines. The $i$-th line contains two integers $D_i$ and $C_i$, separated by a space. Then there are $M$ lines. The $i$-th line contains two integers $U_i$ and $V_i$, separated by a space.

Output one integer, the maximum possible total power. If it is strictly greater than $10^9$, output $-1$. If it is exactly equal to $10^9$, you should output $10^9$.

### Hint $\underline{Sample\ 1}$ This sample satisfies Subtasks 4 and 7. A visualization is given below. An arrow from skill $x$ to skill $y$ means there is a skill link $(x, y)$, i.e., Evirir can use skill $y$ immediately after skill $x$. The large circle in the upper-left corner explains what each number means. :::align{center}  ::: Evirir can change the colors of at most $K = 2$ skills to color $T = 1$. It can change the colors of skills $1$ and $3$ to $1$, and then cast the skill sequence $0 \to 1 \to 2 \to 3 \to 5$. The total power is $(1 \times 3) + (2 \times 2) + (4 \times 4) + (8 \times 5) + (1 \times 2) = 65$. An example that is not a combo is the skill sequence $0 \to 3 \to 4 \to 5$, because $(4, 5)$ is not one of the $M$ skill links. $\underline{Sample\ 2}$ This sample satisfies Subtasks 2, 3, 4, 5, 6, and 7. There are $N = 5$ skills and $M = 4$ skill links. $K = 0$, so Evirir cannot modify the color of any skill. The optimal combo is casting $0 \to 1 \to 2 \to 3 \to 4$. The total power is $(2 \times 1) + (3 \times 1) + (2 \times 1) + (3 \times 2) + (13 \times 4) = 65$. $\underline{Sample\ 3}$ This sample satisfies Subtasks 1, 3, 4, 5, 6, and 7. Since $K = 4$, Evirir can change the colors of skills $1$, $2$, and $3$ to color $T = 0$. The optimal combo is casting $0 \to 1 \to 2 \to 3$. The total power is $(10^8 \times 1) + (10^8 \times 2) + (10^8 \times 4) + (10^8 \times 8) > 10^9$. Since the maximum possible total power is strictly greater than $10^9$, output $-1$. ### Scoring For all testdata, the input satisfies the following Constraints: - $1 \le N \le 10^4$ - $0 \le M \le \min\left(10^5, \frac{N(N - 1)}{2}\right)$ - For all $0 \le i \le N - 1$, $1 \le D_i \le 10^8$ - For all $0 \le i \le N - 1$, $0 \le C_i \le N - 1$ - $0 \le T \le N$. Note that $T$ may equal $N$, i.e., a color that is not used. - $0 \le K \le N$ - For all $0 \le i \le M - 1$, $0 \le U_i, V_i \le N - 1$ and $U_i \neq V_i$ - For all $0 \le i \le M - 1$, the pairs $(U_i, V_i)$ are all distinct. - It is guaranteed that the skill links do not form a cycle. In other words, it is impossible to build a combo that uses the same skill twice. | Subtask | Points | Additional Constraints | | :---: | :---: | :---: | | $1$ | $8$ | $M = N - 1$, and for all $0 \le i \le M - 1$, $(U_i, V_i) = (i, i + 1)$. $K = N$ | | $2$ | $9$ | $M = N - 1$, and for all $0 \le i \le M - 1$, $(U_i, V_i) = (i, i + 1)$. $K = 0$ | | $3$ | $31$ | $M = N - 1$, and for all $0 \le i \le M - 1$, $(U_i, V_i) = (i, i + 1)$. $N \le 50$ | | $4$ | $14$ | $N \le 50$ | | $5$ | $17$ | $M = N - 1$, and for all $0 \le i \le M - 1$, $(U_i, V_i) = (i, i + 1)$. $N \le 300$ | | $6$ | $17$ | $M = N - 1$, and for all $0 \le i \le M - 1$, $(U_i, V_i) = (i, i + 1)$. | | $7$ | $4$ | --- | Translated by ChatGPT 5