AT_tkppc2015_h 私、木になります (I become a tree)

当你回到学校去参观下一个社团时，发现有个少女正在吃威士忌巧克力。 然后她看到 joisino 姐姐后，邀请她一起玩游戏。 joisino 姐姐非常喜欢游戏，所以当然答应了一起玩。 于是她们决定玩一个叫做“我变成树了”的游戏。这个游戏使用 $N$ 个城市和 $M$ 条道路。 一开始，$N$ 个城市通过 $M$ 条道路互相连通。 此时，第 $i$ 条道路（$1 \leq i \leq M$）连接着城市 $A_i$（$1 \leq A_i \leq N$）和 $B_i$（$1 \leq B_i \leq N$）。 游戏的规则是在保证城市之间依然互相连通的前提下，依次移除道路。 她非常聪明，所以在游戏开始前就已经计划好了每一步要在什么时候移除哪条道路。 这个计划由 $Q$ 个操作组成，第 $i$ 个操作（$1 \leq i \leq Q$）尝试移除第 $D_i$ 条道路（$1 \leq D_i \leq M$）。 被移除的道路都是游戏开始时就存在的，并且同一条道路不会被移除多次。 然而，现在她因为吃了威士忌巧克力有点醉了，按照这个计划移除道路时，有可能会违反游戏规则。 此外，每个操作 $i$ 都有一个重要度 $G_i$。 如果操作 $i$ 失败，也就是说执行该操作会导致城市之间不再互相连通，那么她就不会执行这个操作，并因此感到 $G_i$ 的沮丧。 因此，游戏结束时，她的沮丧值等于所有失败操作的重要度之和。 joisino 姐姐不希望她太沮丧，所以决定在游戏过程中任选时机，最多添加 $P$ 条道路。 不过，不能在游戏开始时已经由一条道路直接连接的两个城市之间再添加新的道路。 请计算，在可以添加最多 $P$ 条道路的情况下，游戏结束时她的沮丧值的最小可能值。

输入以如下格式从标准输入读入。 > $N$ $M$ $Q$ $P$ > $A_1$ $B_1$ > $A_2$ $B_2$ > ... > $A_M$ $B_M$ > $D_1$ $G_1$ > $D_2$ $G_2$ > ... > $D_Q$ $G_Q$ - 第 1 行包含城市数 $N$（$1 \leq N \leq 10^5$）、初始道路数 $M$（$N-1 \leq M \leq 3 \times 10^5$）、操作数 $Q$（$1 \leq Q \leq M$）、最多可添加的道路数 $P$（$0 \leq P \leq 10^9$），以空格分隔。 - 接下来 $M$ 行，第 $i$ 行包含第 $i$ 条道路的信息 $A_i$ 和 $B_i$，以空格分隔。 - 接下来 $Q$ 行，第 $i$ 行包含第 $i$ 个操作的信息 $D_i$ 和 $G_i$（$1 \leq G_i \leq 10^9$），以空格分隔。 - 保证 $A_i \neq B_i$。 - 对于 $i \neq j$，保证 $A_i \neq A_j$ 或 $B_i \neq B_j$。 - 对于 $i \neq j$，保证 $D_i \neq D_j$。

请输出游戏结束时她的最小沮丧值。输出末尾需换行。

### 配分 本题有部分分。 - 数据集 1 满足 $N \leq 10^4$、$M \leq 10^4$、$P = 0$，全部正确可得 10 分。 - 数据集 2 满足 $P = 0$，全部正确可得 10 分。 - 数据集 3 无额外限制，全部正确可得 120 分。 ### 样例解释 1 在这种情况下，最初城市之间如上图所示相连，最终会变成下图所示。此时她无法移除第 2 条道路，游戏结束时她会沮丧 $10$。  ### 样例解释 2 #### 输出样例2 ``` 11 ``` 在这种情况下，最初城市之间如上图所示相连，在执行操作 2 之前，在城市 1 和城市 4 之间添加一条道路，最终会变成下图所示。此时她无法移除第 3 条道路，游戏结束时她会沮丧 $11$。 这个测试用例包含在数据集 3 中。  这个测试用例包含在数据集 3 中。 由 ChatGPT 4.1 翻译