D. Tourists
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Example
Input
8 4 11
1 4 8 1
6 4
6 3
3 7
6 5
5 1
1 2
1 8
q 4
t 3 4 5
t 2 2 7
q 4
e 5 10
e 1 5
q 4
t 1 1 5
t 2 2 1
q 1
q 2
Output
0
-1
9
4
-7