2
10 3
100 50
2
1 1 2 5
1 2 2 9
