Input
20 3 2
10 99
2 4 3
20 10 40
4 15
10 80
Output
20
Input
20 3 2
10 99
2 4 3
200 100 400
4 15
100 800
Output
200