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

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

1 секунда

64 мегабайти

Легка

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

На жаль, цей масив досить нудний, оскільки всі його елементи нульові. Щоб розвеселити Алісу, Боб вирішив змінити масив за спеціальним правилом.

Бобу дозволено зробити $m$ змін, кожна із яких визначається так. Дано два числа $x$ та $d$ . Боб обирає позицію $i$ ( $1 \leq i \leq n$ 1 \leq i \leq n) і для кожного $j$ із $[1, n]$ додає до $j$ -го елемента число $x + d \cdot dist (i, j)$ x + d \cdot \text{dist}(i, j), де $dist (i, j)$ \text{dist}(i, j) — відстань між елементами $i$ та $j$ : $dist (i, j) = ∣ i - j ∣$ \text{dist}(i, j) = |i - j|.

Наприклад, якщо у Аліси масив $[2, 1, 2, 2]$ [2, 1, 2, 2], і Боб обирає позицію $3$ з $x = - 1$ x = -1, $d = 2$ d = 2,тоді масив стане:

$[2 - 1 + 2 \cdot 2, 1 - 1 + 2 \cdot 1, 2 - 1 + 2 \cdot 0, 2 - 1 + 2 \cdot 1] = [5, 2, 1, 3]$ [2 - 1 + 2 \cdot 2,\ 1 - 1 + 2 \cdot 1,\ 2 - 1 + 2 \cdot 0,\ 2 - 1 + 2 \cdot 1]=[5, 2, 1, 3]

Боб не може вибрати позицію $i$ поза межами масиву.

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

Яке максимальне середнє арифметичне може отримати Боб?

Вхідні дані

У першому рядку задано два цілі числа $n$ та $m$ ( $1 \leq n, m \leq 1 0^{5}$ 1 \leq n, m \leq 10^5) — кількість елементів у масиві та кількість змін.

У кожному із наступних $m$ рядків — по два числа $x_{i}$ x_i та $d_{i}$ d_i ( $1 0^{- 3} \leq x_{i}, d_{i} \leq 1 0^{3}$ 10^{-3} \leq x_i, d_i \leq 10^3) — параметри для $i$ -ої зміни.

Вихідні дані

Виведіть максимальне значення середнього арифметичного елементів масиву, яке може отримати Боб, з абсолютною чи відносною похибкою не більше $1 0^{- 7}$ 10^{-7}.

Приклади

Приклад 1

Приклад 2