F. Xattotlar

Samarqanddagi qadimiy qo‘lyozma N ta bobdan iborat, i-bob pᵢ sahifa. Uni K ta xattot ko‘chiradi.

Har bir xattotga ketma-ket keluvchi boblar bo‘lagi beriladi, har bir xattot kamida bitta bob oladi va har bir bob aynan bitta xattotga tegadi. Xattotlar bir vaqtda ishlaydi va bir xil tezlikda yozadi, shuning uchun ish eng ko‘p sahifa olgan xattot tugatganda tugaydi.

Boblarni shunday taqsimlangki, eng ko‘p sahifa olgan xattotning sahifalari soni iloji boricha kam bo‘lsin. Shu sonni chiqaring.

Kirish ma’lumotlari

Birinchi qatorda N va K. Ikkinchi qatorda N ta butun son: p₁, p₂, …, p_N.

Chiqish ma’lumotlari

Bitta butun son — eng ko‘p sahifa olgan xattotning sahifalari sonining eng kichik qiymati.

Cheklovlar

• 1 ≤ K ≤ N ≤ 10⁵
• 1 ≤ pᵢ ≤ 10⁹
• Yig‘indi 10¹⁴ gacha: C++ da long long ishlating.

1-misol: 10 + 20 + 30 = 60 | 40 + 50 = 90 | 60. 89 sahifa bilan uchta xattot yetmaydi.

2-misol: 7 + 2 + 5 = 14 | 10 + 8 = 18.