Input
2 2
2 3
3 5
Output
3
Input
3 2
1 2 3
3 4
Output
4
Input
3 2
4 5 6
1 2
Output
0