input:

5 9 5
2 6 11 19 25
10011
7 5
3 1
4 5
2 1
7 5

output:

45
6
34
6
45