5 11
1 2 3 4 5
2 -1 0 5
0 -1 2 4 100 1
0 1 1 3 100 3
2 2 1 5
2 2 0 5
1 2 -1 1 3
2 5 0 1
2 5 0 2
2 5 0 3
2 5 0 4
2 5 0 5