Алиса и Боб

В который раз Алисе в день рождения вручили массив с 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 + 2 * 2,1-1 + 2 * 1,2-1 + 2 * 0,2-1 + 2 * 1] = [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.

0