case 2 failed:
input:
5 5 3 1
5 14 15 13 3
1 0
3 0
3 1
2 3 3
expected:
-1
got:
1000000000