يمتلك Paul شركة لتقديم الطعام، وأعمالها مزدهرة. لدى الشركة $k$ فرق لتقديم الطعام، كل منها مسؤول عن مجموعة واحدة من المعدات. تقبل الشركة كل أسبوع $n$ طلبات لتقديم الطعام في مناسبات مختلفة. ولكل طلب ترسل فريقاً مع معداته إلى مكان المناسبة. يوصل الفريق الطعام، ويجهز المعدات، ويشرح للمضيف كيفية استخدامها وتقديم الطعام. وبعد المناسبة، يكون المضيف مسؤولاً عن إعادة المعدات إلى شركة Paul.

صورة من Wikimedia Commons

للأسف، يكون عدد الفرق في بعض الأسابيع أقل من عدد الطلبات، ولذلك قد تضطر بعض الفرق إلى خدمة أكثر من مناسبة. في هذه الحالات، لا تستطيع الشركة انتظار إعادة المضيف للمعدات، ويجب أن تُبقي الفريق في الموقع لنقل المعدات إلى مكان آخر. لدى الشركة تقدير دقيق لتكلفة نقل مجموعة معدات من أي مكان إلى أي مكان آخر. انطلاقاً من هذه التكاليف، يريد Paul إعداد Advance Catering Map لتلبية الطلبات مع تقليل التكلفة الإجمالية لنقل المعدات (بما في ذلك النقل الأول)، حتى لو اقتضى ذلك عدم استخدام جميع الفرق المتاحة. يحتاج Paul إلى مساعدتك لكتابة برنامج ينجز هذه المهمة. الطلبات مرتبة تصاعدياً بحسب أوقات المناسبات، ومختارة بحيث يتوفر، لكل $i<j$، وقت كافٍ لنقل المعدات المستخدمة في الطلب رقم $i$ إلى موقع الطلب رقم $j$.

الإدخال

يحتوي السطر الأول من الإدخال على عددين صحيحين $n$ ($1 \le n \le 100$) و$k$ ($1 \le k \le 100$)، وهما عدد الطلبات وعدد فرق تقديم الطعام، على الترتيب. تليهما $n$ أسطر، يحتوي السطر رقم $i$ منها على $n-i+1$ أعداد صحيحة بين $0$ و$1\,000\,000$، شاملة الطرفين. العدد رقم $j$ في السطر رقم $i$ هو تكلفة نقل مجموعة معدات من الموقع $i$ إلى الموقع $i+j$. تقع الشركة في الموقع $1$، وتقع الطلبات $n$ في المواقع من $2$ إلى $n+1$.

الإخراج

اعرض أقل تكلفة نقل لتلبية جميع الطلبات. (لا يشمل هذا المبلغ تكلفة إعادة المعدات إلى شركة تقديم الطعام.)

أمثلة

الإدخال 1

3 2
40 30 40
50 10
50

الإخراج 1

80

الإدخال 2

3 2
10 10 10
20 21
21

الإخراج 2

40