Надоедливый подарок
На день рождения Алисе снова подарили массив из n элементов. Уже третий год подряд!
И что еще хуже, он очень скучный, полностью заполненный нулями. Боб решил изменить массив определенным образом, чтобы развеселить Алису.
Боб выбрал m изменений следующего вида. Для некоторых целых чисел x и d он выбирает произвольную позицию i (1 ≤ i ≤ n) и для всех j ∈ [1,n] добавляет x + d * dist(i,j) к значению j-го элемента. dist(i,j) – расстояние между элементами i и j, то есть dist(i,j) = |i-j|.
Например, если у Алисы в данный момент есть массив [2,1,2,2], и Боб выбирает позицию 3 для x=-1 и d=2, то массив становится:
[2-1+22,1-1+21,2-1+20,2-1+21]=[5,2,1,3]
Боб не может выбирать позицию i за пределами массива.
Алиса будет максимально счастлива, если элементы массива будут как можно больше. Боб решил, что среднее арифметическое прекрасно подойдет в качестве метрики.
Какое максимальное значение среднего арифметического Боб может получить?
Входные данные
В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 10^5) – количество элементов в массиве и количество изменений.
В каждом из следующих m строк задано по два числа x[i] и d[i] (10^(-3) ≤ x[i], d[i] ≤ 10^3) – параметры для i-го изменения.
Выходные данные
Выведите максимальное значение среднего арифметического элементов массива, которое Боб может получить, с точностью до 10^(-7).