Problem Description

When I returned to the club room, I saw a girl eating whiskey bonbons. When she saw Joisino, she asked if she would like to play a game together. Joisino loves games, so she decided to join.

They decided to play a game called "I become a tree." In this game, they use $ N $ cities and $ M $ roads. Initially, the $ N $ cities are connected by $ M $ roads such that they can travel between any two cities. Road $i(1 \leq i \leq M)$ connects city $A_i(1 \leq A_i \leq N)$ and city $B_i(1 \leq B_i \leq N)$. The game involves removing roads while ensuring that the cities remain connected.

She is very smart and has planned which roads to remove and when before the game starts. This plan consists of $ Q $ operations, where the $i(1 \leq i \leq Q)$th operation involves removing road $D_i(1 \leq D_i \leq M)$. The roads to be removed are chosen from those present at the start of the game, and the same road is not removed multiple times. However, she is a bit tipsy from eating whiskey bonbons, so she might violate the game rules by removing roads according to her plan.

She also has an importance value $ G_i $ for each operation $ i $. If operation $ i $ fails, meaning that it would disconnect the cities, she will be upset by $ G_i $. Therefore, at the end of the game, she will be upset by the total importance of failed operations.

Joisino doesn't want her to be too upset, so she decided to add up to $ P $ roads at any point during the game. However, she cannot add a road between two cities that were connected by a single road at the start of the game.

Joisino decided to calculate the minimum amount of upsetness she could cause at the end of the game by performing these actions.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains the number of cities $N(1 \leq N \leq 10^5)$, the number of roads at the start of the game $M(N-1 \leq M \leq 3*10^5)$, the number of operations $Q(1 \leq Q \leq M)$, and the number of roads that can be added $P(0 \leq P \leq 10^9)$, separated by spaces.
• The next $ M $ lines contain the information of the roads, where the $ i $th line contains $ A_i $ and $ B_i $ separated by spaces.
• The next $ Q $ lines contain the information of the operations, where the $ i $th line contains $ D_i $ and $G_i(1 \leq G_i \leq 10^9)$, separated by spaces.
• It is guaranteed that $A_i \neq B_i$.
• It is guaranteed that for $i \neq j$, either $A_i \neq A_j$ or $B_i \neq B_j$.
• It is guaranteed that for $i \neq j$, $D_i \neq D_j$.

Output Format

Output the minimum amount of upsetness she will have at the end of the game. End the output with a newline.

Sample Input and Output

Sample Input #1

3 3 2 0
3 1
2 3
2 1
3 15
2 10

Sample Output #1

10

Sample Input #2

4 4 3 1
2 1
2 3
2 4
3 1
4 7
1 17
3 11

Sample Output #2

14

Sample Input #3

4 6 4 5
3 1
2 1
3 4
4 1
2 3
2 4
5 23
3 18
6 5
4 14

Sample Output #3

None

Notes/Hints

Scoring

This problem has partial points.

• Dataset 1 satisfies $N \leq 10^4$, $M \leq 10^4$, $ P = 0 $, and correct answers will earn 10 points.
• Dataset 2 satisfies $ P = 0 $, and correct answers will earn 10 points.
• Dataset 3 has no additional constraints, and correct answers will earn 120 points.

Sample Explanation 1

In this case, initially, the cities are connected as in the top diagram, and eventually, they will be in the shape shown in the bottom diagram. In this case, she cannot remove road $ 2 $, and at the end of the game, she will be upset by $ 10 $.

Sample Explanation 2

In this case, initially, the cities are connected as in the top diagram, and by creating a road between cities $ 1 $ and $ 4 $ before performing operation $ 2 $, they will eventually be in the shape shown in the bottom diagram. In this case, she cannot remove road $ 3 $, and at the end of the game, she will be upset by $ 11 $. Note that this case is included in Dataset 3.

见题面 Input 部分

见题面 Output 部分