Alice 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≤i≤n) and for every j∈[1,n] adds x+d⋅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⋅2, 1−1+2⋅1, 2−1+2⋅0, 2−1+2⋅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≤n,m≤105) — the number of elements of the array and the number of changes.
Each of the next m lines contains two integers xi and di (−103≤xi,di≤103) — 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

这题意思是原数列都是0 然后执行多次操作 每次操作给一个x和d 每个数加上x+dis(i,j)
要求最后数列最大的平均值
这样并不需要对每个数进行操作 直接对整个数列的和进行操作，每次一定要加的是x*n 然后根据d的正负判断i的最优位置，通过求和公式求出公式

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
long long n,m;
long long x,d;
int main(void){
    scanf("%lld%lld",&n,&m);
    long long ans=0;
    while(m--){
        scanf("%lld%lld",&x,&d);
        ans+=x*n;
        if(d<0){
            long long dist_sum=0;
            if(n&1){
                dist_sum=((n-1)*(n+1))/4;
            }
            else{
                dist_sum=n*n/4;
            }
            ans+=dist_sum*d;
        }
        else{
            long long dist_sum=(n-1)*n/2;
            ans+=dist_sum*d;
        }
    }
    printf("%.15lf\n",(double)ans/n);
    return 0;
}