케이터링

폴은 케이터링 회사를 운영하고 있고, 일이 아주 많다. 회사에는 케이터링 팀이 $k$개 있고 각 팀은 케이터링 장비 한 세트를 맡는다. 회사는 매주 서로 다른 행사에 대한 케이터링 요청을 $n$건 받는다. 요청이 들어오면 팀 하나가 장비를 가지고 행사 장소로 간다. 팀은 음식을 배달하고 장비를 설치한 뒤, 장비를 어떻게 쓰고 음식을 어떻게 내는지 주최자에게 알려 준다. 행사가 끝나면 주최자가 장비를 회사로 돌려보낸다.

어떤 주에는 팀 수가 요청 수보다 적어서 한 팀이 행사 두 곳 이상을 맡아야 한다. 이때 회사는 주최자가 장비를 돌려보낼 때까지 기다릴 수 없으므로, 팀이 현장에 남아 장비를 다음 장소로 바로 옮긴다. 장비 한 세트를 어느 장소에서 다른 어느 장소로 옮기는 비용은 회사가 정확히 알고 있다. 폴은 요청 $n$건을 모두 처리하면서 장비 이동 비용의 합을 최소로 하는 계획을 세우려고 한다. 회사에서 처음 출발하는 이동의 비용도 합에 넣는다. 팀을 $k$개보다 적게 써도 된다.

요청은 행사 시각이 이른 순서로 정렬되어 있고, $i < j$인 임의의 두 요청에 대해 $i$번째 요청에 쓴 장비를 $j$번째 요청 장소로 옮길 시간이 충분하다.

첫째 줄에 요청 수 $n$ ($1 \le n \le 100$)과 케이터링 팀 수 $k$ ($1 \le k \le 100$)가 주어진다. 다음 $n$개 줄 중 $i$번째 줄에는 0 이상 1000000 이하의 정수가 $n - i + 1$개 주어진다. $i$번째 줄의 $j$번째 수는 장비 한 세트를 장소 $i$에서 장소 $i + j$로 옮기는 비용이다. 회사는 장소 1에 있고, 요청 $n$건은 장소 2부터 장소 $n + 1$까지에 하나씩 있다.

요청을 모두 처리하는 데 드는 최소 이동 비용을 출력한다. 이 값에는 장비를 회사로 되돌리는 비용이 들어가지 않는다.

서로 다른 두 팀이 같은 장소로 갈 수는 없다. 팀이 둘 이상 있을 수 있는 장소는 출발 장소뿐이다.