Input
6 2 3
2 2 2 2 1 1
Output
2
Input
2 5 1
5 8
Output
9