Input
1 1 0 4
2 3
0 1
Output
3
Input
2 3 0 20
15 17
23 26
1 4
7 11
15 17
Output
20