Farmer John عبقري محاسبة مدهش أدرك أنه قد ينفد ماله لتشغيل المزرعة. حسب وسجل بدقة ما سينفقه ($1 \le money_{i} \le 10,000$) في كل يوم من الأيام الـ$N$ القادمة ($1 \le N \le 100,000$).

يريد FJ ميزانية لعدد $M$ بالضبط من الفترات المالية المتعاقبة ($1 \le M \le N$)، المسماة «fajomonths». كل فترة تضم يومًا أو أكثر متتالية، وكل يوم يتبع فترة واحدة بالضبط.

يريد ترتيب الفترات لتقليل مصروف الفترة الأعلى إنفاقًا وتحديد حده الشهري.

الإدخال

السطر 1: عددان صحيحان مفصولان بمسافة، $N$ و$M$. الأسطر $2\ldots N+1$: يحتوي السطر $i+1$ على دولارات ينفقها Farmer John في اليوم $i$.

الإخراج

السطر 1: أصغر حد شهري ممكن يستطيع Farmer John التعايش معه.

أمثلة

الإدخال 1

7 5
100
400
300
100
500
101
400

الإخراج 1

500

ملاحظة

إذا جعل أول يومين شهرًا، والثالث والرابع شهرًا، وكلًا من الأيام الثلاثة الأخيرة شهرًا مستقلًا، فلن ينفق أكثر من 500 دولار في أي شهر. أي ترتيب آخر يعطي حدًا شهريًا أدنى أكبر.

مصدر المسألة: USACO، مارس 2007.