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