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