레이팅 미적용Paul은 케이터링 회사를 운영하고 있으며 사업이 번창하고 있다. 회사(c\(om- pa\)ny)에는 \(k\)개의 케이터링 팀이 있고, 각 팀은 케이터링 장비(equ\(ip- me\)nt) 한 세트를 담당한다. 매주 회사는 다양한(v\(ar- io\)us) 행사에 대한 케이터링 요청 \(n\)건을 받는다. 요청마다 케이터링 팀 하나가 장비를 갖고 행사장으로 간다. 팀은 음식을 배달하고 장비를 설치한 뒤, 장비 사용법과 음식 서빙 방법을 주최자에게 알려 준다. 행사가 끝나면 장비를 Paul의 회사로 돌려보내는 것은 주최자의 책임이다. 안타깝게도 어떤 주에는 케이터링 팀 수가 요청 수보다 적어서 일부 팀이 두 개 이상의 행사에 투입되어야 할 수 있다. 이런 경우 회사는 주최자가 장비를 돌려줄 때까지 기다릴 수 없고, 팀을 현장에(\(on-si\)te) 남겨 장비를 다른 장소로 옮기게 해야 한다. 회사는 장비 한 세트를 어느 장소에서 다른 어느 장소로 옮기는 비용을 정확하게 추정하고 있다. 이 비용이 주어질 때, Paul은 장비의 총 이동 비용(첫 이동 비용 포함)을 최소화하면서 요청들을 처리하는 사전 케이터링 계획표를 준비하고 싶다. 가용한 팀을 전부 쓰지 않게 되더라도 상관없다. Paul은 이 작업을 수행하는 프로그램을 작성할 당신의 도움이 필요하다. 요청들은 행사 시각의 오름차순으로 정렬되어 있으며, 임의의 \(i < j\)에 대해 \(i^{th}\)번째 요청에 사용된 장비를 \(j^{th}\)번째 요청의 장소로 운송할 시간이 충분하도록 선택되어 있다.
입력의 첫 줄에는 각각 요청 수와 케이터링 팀 수인 두 정수 \(n\) (\(1 \le n \le 100\))과 \(k\) (\(1 \le k \le 100\))가 주어진다. 이어서 \(n\)개의 줄이 오며, 그중 \(i^{th}\)번째 줄에는 0 이상 1 000 000 이하의 정수 \(n - i + 1\)개가 있다. \(i^{th}\)번째 줄의 \(j^{th}\)번째 수는 장비 한 세트를 장소 \(i\)에서 장소 \(i + j\)로 옮기는 비용이다. 회사는 장소 1에 있고 \(n\)건의 요청은 장소 2부터 \(n + 1\)까지에 있다.
모든 요청을 처리하기 위한 최소 이동 비용을 출력한다. (이 금액에는 장비를 케이터링 회사로 다시 옮기는 비용은 포함되지 않는다.)
3 2
40 30 40
50 10
50
80
3 2
10 10 10
20 21
21
40