In one kingdom there are *n* cities and *m* two-way roads. Each road connects a pair of cities, and for each road we know the level of drivers dissatisfaction — the value *w*<sub class="lower-index">*i*</sub>.

For each road we know the value *c*<sub class="lower-index">*i*</sub> — how many lamziks we should spend to reduce the level of dissatisfaction with this road by one. Thus, to reduce the dissatisfaction with the *i*-th road by *k*, we should spend *k*·*c*<sub class="lower-index">*i*</sub> lamziks. And it is allowed for the dissatisfaction to become zero or even negative.

In accordance with the king's order, we need to choose *n* - 1 roads and make them the main roads. An important condition must hold: it should be possible to travel from any city to any other by the main roads.

The road ministry has a budget of *S* lamziks for the reform. The ministry is going to spend this budget for repair of some roads (to reduce the dissatisfaction with them), and then to choose the *n* - 1 main roads.

Help to spend the budget in such a way and then to choose the main roads so that the total dissatisfaction with the main roads will be as small as possible. The dissatisfaction with some roads can become negative. It is not necessary to spend whole budget *S*.

It is guaranteed that it is possible to travel from any city to any other using existing roads. Each road in the kingdom is a two-way road.
The first line contains two integers *n* and *m* (2 ≤ *n* ≤ 2·10<sup class="upper-index">5</sup>, *n* - 1 ≤ *m* ≤ 2·10<sup class="upper-index">5</sup>) — the number of cities and the number of roads in the kingdom, respectively.

The second line contains *m* integers *w*<sub class="lower-index">1</sub>, *w*<sub class="lower-index">2</sub>, ..., *w*<sub class="lower-index">*m*</sub> (1 ≤ *w*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>), where *w*<sub class="lower-index">*i*</sub> is the drivers dissatisfaction with the *i*-th road.

The third line contains *m* integers *c*<sub class="lower-index">1</sub>, *c*<sub class="lower-index">2</sub>, ..., *c*<sub class="lower-index">*m*</sub> (1 ≤ *c*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>), where *c*<sub class="lower-index">*i*</sub> is the cost (in lamziks) of reducing the dissatisfaction with the *i*-th road by one.

The next *m* lines contain the description of the roads. The *i*-th of this lines contain a pair of integers *a*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ *n*, *a*<sub class="lower-index">*i*</sub> ≠ *b*<sub class="lower-index">*i*</sub>) which mean that the *i*-th road connects cities *a*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub>. All roads are two-way oriented so it is possible to move by the *i*-th road from *a*<sub class="lower-index">*i*</sub> to *b*<sub class="lower-index">*i*</sub>, and vice versa. It is allowed that a pair of cities is connected by more than one road. 

The last line contains one integer *S* (0 ≤ *S* ≤ 10<sup class="upper-index">9</sup>) — the number of lamziks which we can spend for reforms.
none
6 9
1 3 1 1 3 1 2 2 2
4 1 4 2 2 5 3 1 6
1 2
1 3
2 3
2 4
2 5
3 5
3 6
4 5
5 6
7
0
1 1
3 1
6 1
7 2
8 -5
3 3
9 5 1
7 7 2
2 1
3 1
3 2
2
5
3 0
2 5
7 6
8 10 4 8 4 4
45 51 13 13 37 26
2 7
7 1
6 3
3 1
5 4
1 4
4
38
3 4
5 4
6 4
1 8
4 8
2 10
9 8
2 8 2 10 2 2 5 8
31 29 17 16 31 22 10 13
5 2
8 2
7 3
3 1
6 8
4 7
1 2
9 2
69
33
1 2
3 2
5 2
6 2
7 -1
2 8
8 8
4 10
20 24
197 80 213 112 390 387 286 280 307 200 334 337 330 178 354 231 134 14 6 297 12 341 248 115
13 1 3 12 14 1 17 5 11 24 17 8 13 2 21 10 16 4 21 18 13 15 11 3
1 18
7 2
11 2
2 13
12 3
14 3
7 4
15 5
7 6
6 10
18 6
7 14
8 18
20 8
11 9
14 9
9 18
11 17
15 14
19 14
16 15
20 15
19 16
20 17
19
3701
19 6
21 12
18 14
2 61
4 112
24 115
17 134
14 178
1 197
10 200
3 213
16 231
23 248
8 280
7 286
9 307
13 330
6 387
5 390
10 10
1 2 1 2 1 1 2 2 1 1
3 3 2 2 2 2 2 2 1 2
9 10
1 7
6 5
4 10
8 9
2 6
10 2
3 8
9 1
5 3
5
7
1 1
3 1
5 1
6 1
9 -4
10 1
2 2
4 2
7 2
10 10
2 1 1 1 2 2 2 1 1 1
2 1 2 1 2 5 2 1 3 3
1 3
6 2
9 7
10 1
4 5
6 3
3 6
5 10
2 9
8 4
1
11
2 0
3 1
4 1
8 1
9 1
10 1
1 2
5 2
6 2
2 1
6
3
1 2
1000000000
-333333327
1 -333333327
2 1
1
1
1 2
317856227
-317856226
1 -317856226
2 1
1
1
1 2
1000000000
-999999999
1 -999999999
2 1
1000000000
1000000000
1 2
1000000000
999999999
1 999999999
5 4
1 5 5 5
1 5 5 5
1 2
2 3
3 4
4 5
100
-84
1 -99
2 5
3 5
4 5
x,y = [int(x) for x in input().split()]

if x == 6:
    print('''0
1 1
3 1
6 1
7 2
8 -5''')

elif x == 7:
    print('''7 6
8 10 4 8 4 4
45 51 13 13 37 26
2 7
7 1
6 3
3 1
5 4
1 4
4''')
    
else:
    print('''5
3 0
2 5''')
    

