Input
1 8 3
10
Output
3
Input
2 10 1
5 8
Output
1
Input
1 1 3
10
Output
-1