Indian National Olympiad in Informatics

Related:

Online Programming Contest, 9-10 July 2005

IARCS home > OLYMPIAD

Basic Division

Problem 1: Which Marks to Drop?, (K Narayan Kumar, CMI)

To select the Siruseri team to participate in the informatics olympiad, N tests are conducted. Indraneel has participated in these tests and has done quite well.

However, the selection process is complicated. Two out of the N tests are dropped, and the examiners determine which two are to be dropped. Then, the two highest marks among the other tests are identified and the sum of these two marks is the final score obtained by the student.

Suppose there were 8 exams and Indraneel's marks in the 8 exams are as follows:

 55  70  80  50  90  75  70  90

If the first two test marks are dropped, then Indraneel's final score would be 90 + 90 = 180. On the other hand if the third and eighth tests are dropped then Indraneel's score would be 75 + 90 = 165, and so on.

Indraneel would like you to write a program that allows him to find his score for various choices of the pair of tests to be dropped.

Input format

The first line of the input will contain two integers, N and M. N is the total number of tests and M is the number of pairs of tests for which he needs the answers. The next line contains N integers indicating the marks that Indraneel obtained in the N tests. This is followed by M lines each containing a pair of integers indicating a pair of tests to be dropped.

Output format

M lines of output, each containing a single integer. The value on line i should be the final score obtained by Indraneel if the two tests on line i+2 of the input are dropped.

Test data

You may assume 1 ≤ N ≤ 100000 and M ≤ 100000.

Example

We now illustrate the input and output formats using the example described above.

Sample input

8 2
55 70 80 50 90 75 70 90 
1 2 
3 8

Sample output

180
165