Bezdirici hədiyyə
Hər il Alisaya doğum günündə n elementdən ibarət bir massiv hədiyyə edilir. Bu artıq üçüncü ildir ki, ardıcıl olaraq baş verir!
Daha da pisi odur ki, bu massivlər çox darıxdırıcıdır, çünki tamamilə sıfırlardan ibarətdir. Bob, Alisanı əyləndirmək üçün massivi müəyyən bir şəkildə dəyişdirməyə qərar verir.
Bob, aşağıdakı növdə m dəyişiklik seçir. Bəzi tam ədədlər x və d üçün, o, təsadüfi bir i mövqeyi (1 ≤ i ≤ n) seçir və bütün j ∈ [1,n] üçün x + d * dist(i,j) dəyərini j-ci elementin dəyərinə əlavə edir. Burada dist(i,j), i və j elementləri arasındakı məsafəni göstərir, yəni dist(i,j) = |i-j|.
Məsələn, əgər Alisanın hazırda [2,1,2,2] massivi varsa və Bob x=-1 və d=2 üçün 3 mövqeyini seçərsə, massiv belə olur:
[2-1+22,1-1+21,2-1+20,2-1+21]=[5,2,1,3]
Bob, massivdən kənarda olan i mövqeyini seçə bilməz.
Alisa, elementlərin mümkün qədər böyük olmasından ən çox xoşbəxt olacaq. Bob qərara gəlir ki, arifmetik orta bu məqsəd üçün mükəmməl bir metrikadır.
Bob maksimum hansı arifmetik orta dəyəri əldə edə bilər?
Giriş məlumatları:
Birinci sətirdə iki tam ədəd n və m (1 ≤ n, m ≤ 10^5) – massivdəki elementlərin sayı və dəyişikliklərin sayı verilir.
Növbəti m sətirdə hər biri üçün iki ədəd x[i] və d[i] (10^(-3) ≤ x[i], d[i] ≤ 10^3) – i-ci dəyişiklik üçün parametrlər verilir.
Çıxış məlumatları:
Bobun əldə edə biləcəyi elementlərin arifmetik ortasının maksimum dəyərini 10^(-7) dəqiqliklə çıxarın.