P16701 [MCO 2026] 制造连招

龙 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$ 的技能。计算过程如下： | | $s_0$ | $s_1$ | $s_2$ | $s_3$ | $s_4$ | $s_5$ | $s_6$ | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 颜色 $C_{s_i}$ | $7$ | $5$ | $7$ | $7$ | $7$ | $7$ | $6$ | | 伤害 $D_{s_i}$ | $3$ | $2$ | $4$ | $1$ | $5$ | $6$ | $3$ | | 倍率 $B$ | $1$ | $1$ | $1$ | $2$ | $4$ | $8$ | $1$ | | 威力 | $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$ | 因此，这个连招的总威力为 $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$。

### 提示 $\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)$ 两两相异。 - 保证技能连接不会形成环。也就是说，不可能构建一个包含同一技能两次的连招。 | 子任务 | 分值 | 额外限制 | | :---: | :---: | :---: | | $1$ | $8$ | $M = N - 1$，且对所有 $0 \le i \le M - 1$，$(U_i, V_i) = (i, i + 1)$。$K = N$ | | $2$ | $9$ | $M = N - 1$，且对所有 $0 \le i \le M - 1$，$(U_i, V_i) = (i, i + 1)$。$K = 0$ | | $3$ | $31$ | $M = N - 1$，且对所有 $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$，且对所有 $0 \le i \le M - 1$，$(U_i, V_i) = (i, i + 1)$。$N \le 300$ | | $6$ | $17$ | $M = N - 1$，且对所有 $0 \le i \le M - 1$，$(U_i, V_i) = (i, i + 1)$。 | | $7$ | $4$ | --- |