L. Beautiful Trips
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
3 3 2
1 2
2 3
3 1
1 2 4
1 2 4
1 2 0
Output
6
4
Input
6 7 5
1 2
2 3
3 1
1 4
4 5
5 6
6 4
1 2 4 8 16 32
1 4 3
2 5 8
1 6 20
3 4 15
3 6 9
Output
11
40
52
14
41