← 返回题目列表

Codeforces · 1009/C

C. 烦人的礼物

中文机器翻译题面 查看原题

Alice got an array of length $$$n$$$ as a birthday present once again! This is the third year in a row!

And what is more disappointing, it is overwhelmengly boring, filled entirely with zeros. Bob decided to apply some changes to the array to cheer up Alice.

Bob has chosen $$$m$$$ changes of the following form.对于某些整数 $$$x$$$ 和 $$$d$$$,他选择任意位置 $$$i$$$ ($$$1 \le i \le n$$$),并且对于 [1, n]$$$ 中的每个 $$$j \in [1, n]$$$ 将 $$$x + d \cdot dist(i, j)$$$ 添加到第 $$$j$$$ 个单元格的值。 $$$dist(i, j)$$$ 是位置 $$$i$$$ 和 $$$j$$$ 之间的距离(即 $$$dist(i, j) = |i - j|$$$,其中 $$$|x|$$$ 是 $$$x$$$ 的绝对值)。

For example, if Alice currently has an array $$$[2, 1, 2, 2]$$$ and Bob chooses position $$$3$$$ for $$$x = -1$$$ and $$$d = 2$$$ then the array will become $$$[2 - 1 + 2 \cdot 2,~1 - 1 + 2 \cdot 1,~2 - 1 + 2 \cdot 0,~2 - 1 + 2 \cdot 1]$$$ = $$$[5, 2, 1, 3]$$$. Note that Bob can't choose position $$$i$$$ outside of the array (that is, smaller than $$$1$$$ or greater than $$$n$$$).

Alice will be the happiest when the elements of the array are as big as possible. Bob claimed that the arithmetic mean value of the elements will work fine as a metric.

What is the maximum arithmetic mean value Bob can achieve?

输入

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — the number of elements of the array and the number of changes.

接下来的 $$$m$$$ 行包含两个整数 $$$x_i$$$ 和 $$$d_i$$$ ($$$-10^3 \le x_i, d_i \le 10^3$$$) — 第 $$$i$$$ 次更改的参数。

输出

Print the maximal average arithmetic mean of the elements Bob can achieve.

如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。

示例

输入 #1

2 3
-1 3
0 0
-1 -4

输出 #1

-2.500000000000000

输入 #2

3 2
0 2
5 0

输出 #2

7.000000000000000