题目描述

龙 Evirir 正在玩一款电子游戏，它想通过连续释放技能来使总伤害最大化。

Evirir 可以使用 $N$ 个不同的技能，编号为 $0, 1, \ldots, N - 1$。对于每个技能 $i$，它的颜色为 $C_i$，伤害为 $D_i$。共有 $M$ 条技能连接，每条连接是一个技能对 $(U_i, V_i)$，其中 $0 \le i \le M - 1$。

一个连招是一个长度为 $l \ge 1$ 的技能序列 $s_0, s_1, \ldots, s_{l - 1}$，满足对于所有 $0 \le i < l - 1$，$(s_i, s_{i+1})$ 都是这 $M$ 条技能连接之一。题目保证输入中的技能连接不会形成环。也就是说，不可能构建一个包含同一技能两次的连招。

该连招的总威力按如下方式计算。设有一个倍率 $B$，初始时 $B = 1$。对于 $i = 0, 1, \ldots, l - 1$，依次进行：

• 如果 $i = 0$，则不做任何事。
• 否则：
  • 如果技能 $s_i$ 和 $s_{i - 1}$ 的颜色相同，则将 $B$ 乘以 $2$。
  • 如果技能 $s_i$ 和 $s_{i - 1}$ 的颜色不同，则将 $B$ 设为 $1$。
• 然后，技能 $s_i$ 的威力为 $D_{s_i} \times B$。

连招的总威力就是所有已释放技能威力之和。

例如，假设某个连招按顺序包含如下技能：$(3,7)$、$(2,5)$、$(4,7)$、$(1,7)$、$(5,7)$、$(6,7)$、$(3,6)$，其中 $(x, y)$ 表示一个伤害为 $x$、颜色为 $y$ 的技能。计算过程如下：

因此，这个连招的总威力为 $3 + 2 + 4 + 2 + 20 + 48 + 3 = 82$。

显然，Evirir 想要施放一个总威力最大的连招。为此，它安装了一个外挂，可以将任意技能的颜色改成一个固定颜色 $T$。Evirir 最多只能使用这个外挂 $K$ 次（也就是说，最多只能修改 $K$ 个技能的颜色）。

求 Evirir 能达到的最大总威力是多少。如果最大总威力严格大于 $10^9$，输出 $-1$。

输入格式

第一行包含四个用空格分隔的整数 $N$、$M$、$K$ 和 $T$。

接下来有 $N$ 行，其中第 $i$ 行包含两个用空格分隔的整数 $D_i$ 和 $C_i$。

接下来有 $M$ 行，其中第 $i$ 行包含两个用空格分隔的整数 $U_i$ 和 $V_i$。

输出格式

输出一个整数，表示可能的最大总威力。如果它严格大于 $10^9$，则输出 $-1$。如果它恰好等于 $10^9$，则应输出 $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

提示

提示

$\underline{样例\ 1}$

这个样例符合子任务 4 和 7。

下面给出一个可视化图示。从技能 $x$ 指向技能 $y$ 的箭头表示存在一条技能连接 $(x, y)$，也就是说 Evirir 可以在技能 $x$ 之后立刻使用技能 $y$。左上角的大圆圈说明了每个数字的含义。

:::align{center} :::

Evirir 最多可以将 $K = 2$ 个技能的颜色改为颜色 $T = 1$。它可以把技能 $1$ 和 $3$ 的颜色改为 $1$，然后施放技能序列 $0 \to 1 \to 2 \to 3 \to 5$。总威力为 $(1 \times 3) + (2 \times 2) + (4 \times 4) + (8 \times 5) + (1 \times 2) = 65$。

一个不是连招的例子是技能序列 $0 \to 3 \to 4 \to 5$，因为 $(4, 5)$ 不是这 $M$ 条技能连接之一。

$\underline{样例\ 2}$

这个样例符合子任务 2、3、4、5、6、和 7。

共有 $N = 5$ 个技能和 $M = 4$ 条技能连接。$K = 0$，因此 Evirir 不能修改任何技能的颜色。 最优连招是施放技能 $0 \to 1 \to 2 \to 3 \to 4$。总威力为 $(2 \times 1) + (3 \times 1) + (2 \times 1) + (3 \times 2) + (13 \times 4) = 65$。

$\underline{样例\ 3}$

这个样例符合子任务 1、3、4、5、6、和 7。

由于 $K = 4$，Evirir 可以将技能 $1$、$2$ 和 $3$ 的颜色改为颜色 $T = 0$。最优连招是施放技能 $0 \to 1 \to 2 \to 3$。总威力为 $(10^8 \times 1) + (10^8 \times 2) + (10^8 \times 4) + (10^8 \times 8) > 10^9$。由于最大可能总威力严格大于 $10^9$，因此输出 $-1$。

评分

对于所有测试用例，输入满足以下限制：

• $1 \le N \le 10^4$
• $0 \le M \le \min\left(10^5, \frac{N(N - 1)}{2}\right)$
• 对所有 $0 \le i \le N - 1$，有 $1 \le D_i \le 10^8$
• 对所有 $0 \le i \le N - 1$，有 $0 \le C_i \le N - 1$
• $0 \le T \le N$。注意，$T$ 可能等于 $N$，即一个未被使用的颜色。
• $0 \le K \le N$
• 对所有 $0 \le i \le M - 1$，有 $0 \le U_i, V_i \le N - 1$ 且 $U_i \neq V_i$
• 对所有 $0 \le i \le M - 1$，数对 $(U_i, V_i)$ 两两相异。
• 保证技能连接不会形成环。也就是说，不可能构建一个包含同一技能两次的连招。