Electrification of a rural area

You are an engineer whose task is to build electrification at the least cost in a rural area with several villages located on two banks of a large river. Power lines are supposed to connect pairs of villages (no lines branching outside villages is allowed). Due to terrain obstacles, only some pairs of villages can be connected, including some pairs located on the opposite sides of the river. Cost of building a power line depends on terrain and distance. For safety and backup reasons, it is prescribed, how many power lines should cross the river exactly. The whole area is considered to be electrified if all villages are connected into one electricity network. Examples of optimally electrified areas are depicted in Figure 1.

Figure 1. a) Villages 0,..,3 are located on the left bank, villages 4,..,8 are located on the right bank. Each edge represents a power line that can be built between the pair of adjacent villages. The label indicates its cost. The network of red edges is the cheapest solution of the total cost 30 (assuming that exactly 2 power lines have to be built across the river). b) Another situation with 8 villages. In this case, 5 power lines are required to be built across the river. The cheapest solution highlighted in red has the total cost 21.

The task

You are given M pairs of villages that can be directly connected by a power line, including costs of building particular connections. It is also known that exactly B power lines should cross the river. Your task is to find a network of power lines electrifying the area with minimal total cost. The total cost is defined as the sum of costs of particular power lines.

---

Input

The first line of the input consists of four integers M, N, D, B separated by space. Value M is the number of possible direct connections, N is the number of villages. Villages are numbered from 0 to N−1. Villages 0,..,D are located on the left bank, villages D+1,..,N−1 are located on the right bank. Value B is the prescribed number of power lines that have to directly connect pairs of villages on opposite banks. Next, there are M lines, each line describes one possible direct connection. The line contains three integers V₁, V₂, C separated by space and representing villages V₁ and V₂ that can be directly connected by a power line of cost C where C is a positive integer.
It holds N ≤ 4000, M ≤ 60000, B ≤ 220 and min(B, R−B) ≤ 6 where R denotes the total number of admissible power lines that go across the river. It also holds that the value of binomial coefficient C(R, B) is at most 10⁵. The cost C of building a power line is at most 900000.

Output

The output is one line containing one integer - the cost of the cheapest electricity network interconnecting all villages. The resulting number is not greater than 2³⁰. It is guaranteed that a solution always exists.

Example 1

Input

15 9 3 2
0 1 2
0 2 3
1 2 4
1 3 3
5 8 5
5 6 4
6 8 2
7 6 3
7 8 3
6 4 4
7 4 5
3 5 7
3 4 9
2 5 8
2 4 6

Output

30

The data and solution of Example 1 are depicted in Figure 1a).

Example 2

Input

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

Output

21

The data and solution of Example 2 are depicted in Figure 1b).

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set