Grades

Time limit1sMemory limit1024 MB

Summary

Insert Juku into a presentation order to maximize the grades he receives, where grades either reflect project value or reciprocate a prior grade.

Level: Medium7 of 10
Topics: Greedy, Prefix sum, Math
Solved: No attempts yet

Problem

Every student in a class must present their own research project. After each presentation, every other student gives the presented project a grade.

Student $A$ grades student $B$ 's project according to the following rule:

If $B$ has not yet graded $A$ 's project, then $A$ gives an honest grade equal to the actual value of $B$ 's project.
If $B$ has already graded $A$ 's project, then $A$ returns exactly the same grade that $A$ received from $B$ .

The teacher has already written a list fixing the order of all presentations, but Juku's name is missing from it. Determine at which position in the list Juku should insert himself so that the total grade he receives is maximized. The student currently at Juku's chosen position and everyone after them shift one place back in the order.

Input

The first line contains the value $V$ of Juku's research project ( $1 \le V \le 1000$ ).

The second line contains the number $N$ of students already on the list ( $1 \le N \le 1\,000\,000$ ).

Each of the next $N$ lines contains the value $V_i$ of one student's research project ( $1 \le V_i \le 1000$ ).

Output

Print two integers on one line. The first is the maximum total grade Juku can receive; the second is the position in the list he must choose to achieve it. The position ranges from $1$ to $N+1$ , where $N+1$ means standing after everyone. If several positions achieve the maximum, print the smallest (earliest) one.

Examples3

Example 1
Input
```
7
6
8
5
9
4
4
4
```
Expected output
```
43 2
```
Example 2
Input
```
5
1
10
```
Expected output
```
10 2
```
Example 3
Input
```
10
1
3
```
Expected output
```
10 1
```