Обридлий подарунок
В котрий раз Алісі на день народження вручили масив з 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).