eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Обридлий подарунок

Обридлий подарунок

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

В котрий раз Алісі на день народження вручили масив з n елементів. Уже третій рік підряд!

І що ще гірше, він дуже нудний, повністю заповнений нулями. Боб вирішив змінити масив певним чином так, щоб звеселити Алісу.

Боб вибрав m змін наступного виду. Для деяких цілих чисел x і d він вибирає довільну позицію i (1in) і для всіх 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 (1n, m10^5) – кількість елементів в масиві і кількість змін.

В кожному наступному з m рядків задано по два числа x[i] і d[i] (10^(-3)x[i], d[i]10^3) – параметри для i-тої зміни.

Вихідні дані

Виведіть максимальне значення середнього арифметичного елементів масиву, яке Боб може отримати, з точністю до 10^(-7).

Приклад

Вхідні дані #1
2 3
-1 3
0 0
-1 -4
Вихідні дані #1
-2.500000000000000
Вхідні дані #2
3 2
0 2
5 0
Вихідні дані #2
7.000000000000000