10 10
1 5 4 2 3 6 10 1 4 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
1 7 10 1
2 5 8
1 9 10 1
2 2 10
2 1 7

应该输出

11
8
20
23
52
41