Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Annoying Present

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAlice got an array of length $$$n$$$ as a birthday present once again! This is the third year in a row!

And what is more disappointing, it is overwhelmengly boring, filled entirely with zeros. Bob decided to apply some changes to the array to cheer up Alice.

Bob has chosen $$$m$$$ changes of the following form. For some integer numbers $$$x$$$ and $$$d$$$, he chooses an arbitrary position $$$i$$$ ($$$1 \le i \le n$$$) and for every $$$j \in [1, n]$$$ adds $$$x + d \cdot dist(i, j)$$$ to the value of the $$$j$$$-th cell. $$$dist(i, j)$$$ is the distance between positions $$$i$$$ and $$$j$$$ (i.e. $$$dist(i, j) = |i - j|$$$, where $$$|x|$$$ is an absolute value of $$$x$$$).

For example, if Alice currently has an array $$$[2, 1, 2, 2]$$$ and Bob chooses position $$$3$$$ for $$$x = -1$$$ and $$$d = 2$$$ then the array will become $$$[2 - 1 + 2 \cdot 2,~1 - 1 + 2 \cdot 1,~2 - 1 + 2 \cdot 0,~2 - 1 + 2 \cdot 1]$$$ = $$$[5, 2, 1, 3]$$$. Note that Bob can't choose position $$$i$$$ outside of the array (that is, smaller than $$$1$$$ or greater than $$$n$$$).

Alice will be the happiest when the elements of the array are as big as possible. Bob claimed that the arithmetic mean value of the elements will work fine as a metric.

What is the maximum arithmetic mean value Bob can achieve?

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — the number of elements of the array and the number of changes.

Each of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$d_i$$$ ($$$-10^3 \le x_i, d_i \le 10^3$$$) — the parameters for the $$$i$$$-th change.

Output

Print the maximal average arithmetic mean of the elements Bob can achieve.

Your answer is considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$.

Examples

Input

2 3

-1 3

0 0

-1 -4

Output

-2.500000000000000

Input

3 2

0 2

5 0

Output

7.000000000000000

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/14/2018 02:53:16 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|