Annoying Gift
For the third consecutive year, Alice received an array with n elements for her birthday!
Unfortunately, the array is quite dull, as it is entirely filled with zeros. To brighten Alice's day, Bob decided to modify the array in a specific way.
Bob planned m modifications of the following type. For given integers x and d, he selects a position i (1 ≤ i ≤ n) and for each j in the range [1, n], he adds x + d * dist(i, j) to the j-th element. Here, dist(i, j) represents the distance between elements i and j, defined as dist(i, j) = |i - j|.
For instance, if Alice's current array is [2, 1, 2, 2], and Bob chooses position 3 with x = -1 and d = 2, the array transforms to:
[2 - 1 + 22, 1 - 1 + 21, 2 - 1 + 20, 2 - 1 + 21] = [5, 2, 1, 3]
Bob cannot select a position i that is outside the array.
Alice will be the happiest if the array elements are as large as possible. Bob decided that maximizing the arithmetic mean would be an excellent measure of success.
What is the maximum arithmetic mean that Bob can achieve?
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 10^5) – the number of elements in the array and the number of modifications.
Each of the following m lines contains two numbers x[i] and d[i] (10^(-3) ≤ x[i], d[i] ≤ 10^3) – parameters for the i-th modification.
Output
Print the maximum value of the arithmetic mean of the array elements that Bob can achieve, with a precision of 10^(-7).