تقول الأسطورة إن St. Patrick طرد جميع الثعابين من Mooland قبل أكثر من ألف سنة. لكنها عادت منذ ذلك الحين! كان يوم القديس باتريك في 17 مارس، لذا ستُحيي Bessie ذكراه بطرد كل الثعابين من Mooland نهائيًا.

لدى Bessie شبكة لالتقاط ثعابين موزعة في $N$ مجموعات على خط $(1 \leq N \leq 400)$. عليها التقاط كل ثعبان في كل مجموعة بترتيب المجموعات على الخط. بعد التقاط مجموعة، يمكنها وضع الثعابين في قفص والبدء بالمجموعة التالية بشبكة فارغة.

تسمح شبكة بحجم $s$ بالتقاط مجموعة من $g$ ثعابين إذا كان $g \leq s$. لكن كل التقاط لمجموعة بحجم $g$ بشبكة حجمها $s$ يهدر مساحة مقدارها $s - g$. يمكن أن تبدأ الشبكة بأي حجم، ويمكن لـBessie تغيير حجمها $K$ مرات $(1 \leq K < N)$.

أخبر Bessie بأقل مساحة مهدرة إجمالية بعد التقاط جميع المجموعات.

الإدخال

يحتوي السطر الأول على $N$ و$K$. يحتوي الثاني على $N$ أعداد صحيحة $a_1,\dots,a_N$، حيث $a_i$ ($0 \leq a_i \leq 10^6$) هو عدد الثعابين في المجموعة رقم $i$.

الإخراج

اطبع عددًا صحيحًا واحدًا يعطي أقل مساحة مهدرة بعد التقاط كل الثعابين.

أمثلة

الإدخال 1

6 2
7 9 8 2 3 2

الإخراج 1

3

ملاحظة

تبدأ الشبكة بحجم 7. بعد المجموعة الأولى، تغيّر Bessie الحجم إلى 9 وتبقيه حتى المجموعة الرابعة، حيث تغيّره إلى 3. إجمالي المساحة المهدرة هو $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.$

مؤلف المسألة: Patrick Zhang