H. National Arena
time limit per test
3 seconds
memory limit per test
500 megabytes
input
standard input
output
standard output
Example
Input
4 3 11
1 3 1
1 7 1
1 5 3
3 1 2 1 3
2 1 1
1 4 2
1 5 2
1 6 2
3 1 3 1 3
2 2 2
3 1 2 2 3
Output
15
27
15