Input
7 4
1 3
1 2
2 0 1
2 1 2
Output
4
3
Input
10 9
2 2 9
1 1
2 0 1
1 8
2 0 8
1 2
2 1 3
1 4
2 2 4
Output
7
2
10
4
5