Input
2 3
1 2
1 1 1 1
1 1 1 2
1 1 2 2
Output
1
1
1
Input
4 2
1 3 2 4
4 1 4 4
1 1 2 3
Output
3
5