XH and a Sheet of paper

内存限制: 128M   时间限制: 1S

题目描述


输入

输出

样例输入

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

样例输出

7
2
10
4
5