You may have heard of "spooky action at a distance", or you may have not. It doesn't matter. There exists a line of particles, of which the
particle and the
particle are quantum entangled. Note that what is described in this problem is not how quantum entanglement really works. Each particle has an electric charge
. You happen to know the electric charges of all
particles in order.
When you look at a particle , due to the fact that it is entangled, it will instantaneously have the charge of particle
, and particle
will have the charge of particle
. You can only look at a maximum of
particles before you become blinded. Thus, you are curious: what is the maximum sum of the charges of the particles
to
, inclusive, if I look at EXACTLY
particles? Note that you can look at a particle at one position multiple times.
You must answer of these questions. These questions must be answered online.
Input Specification
The first line will contain three integers
.
The second line will contain integers,
.
The next lines will each contain two integers,
, a question as defined above.
After each question, you must output the answer before you will receive the next question. In some languages, you may need to flush in order for the interactor to receive your answer. The interactor may take up to 1.5 seconds of the time limit.
Output Specification
Output lines. On the
line, output one integer: the maximum sum of charges of the particles in
.
Subtasks
Subtask 1 [14%]
Subtask 2 [27%]
Subtask 3 [59%]
No additional constraints.
Sample Input 1
7 3 5
3 4 -5 8 3 1 0
1 3
1 4
2 7
3 6
3 3
Sample Output 1
10
18
14
10
3
Explanation For Sample 1
For the first question, if we choose and look
times, we get the line of particles
3 4 3 8 -5 1 0
, whose sum of charges from to
is
. It turns out, this is the maximum possible sum.
Comments