input1:

2 11 10
10
12 15
10 9
6 9
14 4
9 20
9 17
10 9
20 15
8 12
10 3

output1:

163
101
97
55
209
179
101
171
129
41

input2:

2 20 2
10
13 9
10 10

output2

193
209