RT，此题曾有人提供过hack数据，但是现在看不了了，特此提供一组hack数据以造福后人。

input:

6 
2 8 6 5 11 53 
1 2 
1 3 
1 4 
3 5 
3 6
4
1 6 10
2 5 100
1 4 1000
2 4 1 

output:

51
8
0
1004