Eating instant noodles is prohibited in the dormitories of KSA. However, Gaon, who was extremely hungry, tries to hide $N$ instant noodles in his room, avoiding the eyes of the Department of Student Life. Each instant noodle has a size of $2, 4, \cdots, 2N$.

There are $K$ places to hide the instant noodles in Gaon's room. Exactly $C_i$ instant noodles can be hidden in the $i$-th place. $(1 \le i \le K)$

Gaon must hide all the instant noodles he has, and the sum of the number of instant noodles that can be hidden across all places is equal to the total number of instant noodles he has. That is, $N = \sum_{i=1}^K C_i$.

The $i$-th place has an accessibility value of $A_i$, and the risk of the $i$-th place is defined as follows:

Here, the median of a sequence of length $n$ is defined as the arithmetic mean of the $\frac{n}{2}$-th smallest value and the $(\frac{n}{2}+1)$-th smallest value when $n$ is even, and the $\frac{n+1}{2}$-th smallest value when $n$ is odd. For example, the median of $[11, 16, 18, 12, 14]$ is $14$, and the median of $[8, 10, 18, 12, 14, 2]$ is $11$.

Help Gaon find a way to minimize the sum of the risks of all places.

Input

The first line contains two space-separated integers $N$ and $K$.

The $i$-th line of the following $K$ lines contains two space-separated integers $C_i$ and $A_i$.

Output

Print the minimum possible sum of the risks of all places. It is guaranteed that the answer is an integer under the given conditions.

Constraints

• $1 \le K \le 2 \times 10^5$
• $K \le N \le 10^9$
• $C_i \ge 1$
• $\sum_{i=1}^K C_i = N$
• $1 \le A_i \le 1000$

Scoring

Examples

Input 1

5 2
4 3
1 1

Output 1

23

Input 2

8 3
2 3
3 5
3 4

Output 2

85