Problem Description

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:

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$.

Input Format

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 Format

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$.

6 7 2 1
3 1
2 3
4 1
5 2
1 5
2 0
0 1
3 4
2 3
0 3
3 5
1 2
0 5

65

5 4 0 5
2 0
3 1
2 0
3 0
13 0
0 1
1 2
2 3
3 4

65

4 3 4 0
100000000 0
100000000 1
100000000 2
100000000 3
0 1
1 2
2 3

-1

Hint

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.

Translated by ChatGPT 5