Annoying Gift#8786
Alice has received an array of elements for her birthday for the third year in a row!
Unfortunately, the array is rather boring since all its elements are zero. To cheer Alice up, Bob decides to modify the array using a special rule.
Bob is allowed to make modifications, each defined as follows. Given two numbers and , Bob selects a position (1 \leq i \leq n) and for every in , he adds x + d \cdot \text{dist}(i, j) to the -th element. Here, \text{dist}(i, j) is the distance between elements and , i.e., \text{dist}(i, j) = |i - j|.
For example, if Alice's array is [2, 1, 2, 2] and Bob chooses position with x = -1, d = 2,the resulting array will be:
[2 - 1 + 2 \cdot 2,\ 1 - 1 + 2 \cdot 1,\ 2 - 1 + 2 \cdot 0,\ 2 - 1 + 2 \cdot 1] = [5, 2, 1, 3]
Bob cannot select a position that is outside the array.
Alice will be happiest if the elements of the array are as large as possible. Bob decided that maximizing the arithmetic mean is the best way to quantify this.
What is the maximum arithmetic mean Bob can achieve?
The first line contains two integers and (1 \leq n, m \leq 10^5) — the number of elements in the array and the number of modifications.
Each of the next lines contains two numbers x_i and d_i (10^{-3} \leq x_i, d_i \leq 10^3) — the parameters for the -th modification.
Print the maximum arithmetic mean Bob can achieve, with absolute or relative error not exceeding 10^{-7}.
Example 1
Example 2