Món quà phiền toái

Cho một mảng gồm $n$ phần tử, ban đầu tất cả đều bằng $0$.

Ta sẽ thực hiện $m$ thao tác. Thao tác thứ $k$ được cho bởi hai số nguyên $x_k$ và $d_k$: ta tự chọn một vị trí $i$ bất kì ($1\le i\le n$), rồi với mọi $j\in [1,n]$ cộng thêm $x_k+d_k·|i-j|$ vào phần tử thứ $j$.

Vị trí $i$ được chọn độc lập cho từng thao tác, và bắt buộc phải nằm trong đoạn $[1,n]$.

Ví dụ, nếu mảng đang là $[2,1,2,2]$ và ta chọn vị trí $i=3$ cho thao tác với $x=-1$, $d=2$ thì mảng trở thành $[2-1+2·2,1-1+2·1,2-1+2·0,2-1+2·1]=[5,2,1,3]$.

Hãy tìm giá trị trung bình cộng lớn nhất của các phần tử trong mảng sau khi thực hiện xong cả $m$ thao tác.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, dòng thứ $k$ chứa hai số nguyên $x_k$ và $d_k$.

Dữ liệu ra

In ra một số thực duy nhất: giá trị trung bình cộng lớn nhất có thể đạt được.

Đáp án được coi là đúng nếu sai số tuyệt đối hoặc sai số tương đối so với đáp án chuẩn không vượt quá ${10}^{-6}$.

Ràng buộc

• $1\le n,m\le {10}^5$
• $-{10}^3\le x_k,d_k\le {10}^3$

Ví dụ