Input:
10 12
100 200 300 400 500 600 700 800 900 1000
1 3
4 8
10 2
3 10
10 8
4 1
2 4
7 9
3 9
8 7
9 5
6 5

Output:
4900 1000