Input
4 3
1 2 3 4
1 1 2 1
1 1 1 1
2 3
Output
2
Input
2 3
1 2
1 2 2 1
2 3
2 4
Output
0
-1