## GlobeX Cup '19 S4 - Ninjaclasher's Wrath 2

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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 .

#### 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.