검표원

Byteasar는 Byteburg와 Bitwise를 잇는 급행열차의 검표원이다. 열차는 진행 순서대로 번호가 매겨진 $n$개의 역에 정차하며, 역에는 $1$번부터 $n$번까지 번호가 붙어 있다. 새 급여 제도에서 그의 보수는 한 번의 운행 동안 검표한 서로 다른 승객의 수에 따라 정해지므로, 그는 되도록 많은 승객을 검표하려 한다. 같은 승객을 두 번 이상 검표해도 추가 보수는 없다.

이웃한 두 역 사이의 구간에서 Byteasar는 그 순간 열차에 타고 있는 모든 승객을 한꺼번에 검표할 수 있다. 그는 한 번의 운행에서 정확히 $k$번 검표하기로 정했다. 각 검표는 어떤 역을 출발한 직후의 구간(역 $s$와 역 $s+1$ 사이의 구간)에서 이루어지며, 그 구간에 타고 있는 모든 승객이 검표된다.

운행 전에 Byteasar는 어느 역에서 타 어느 역에서 내리는 승객이 몇 명인지 정리한 표를 받는다. 역 $i$에서 타 역 $j$($i < j$)에서 내리는 승객은 역 $i$부터 역 $j-1$까지의 모든 구간에서 열차에 타고 있으므로, 역 $s$를 출발한 직후에 하는 검표는 $i \le s \le j-1$일 때 그 승객을 검표한다. 한 번이라도 검표된 승객은 몇 번 검표되든 딱 한 번만 센다.

$k$번의 검표 구간을 잘 골라 검표되는 서로 다른 승객의 수를 최대로 만들고, 그 최댓값을 구하여라.

첫째 줄에 두 정수 $n$과 $k$ ($1 \le k < n \le 600$, $k \le 50$)가 공백 하나로 구분되어 주어진다. 각각 역의 수와 Byteasar가 할 검표 횟수를 뜻한다. 역은 진행 순서대로 $1$번부터 $n$번까지 번호가 매겨져 있다.

다음 $n-1$개의 줄에 승객 정보가 주어진다. $i+1$번째 줄에는 $n-i$개의 음이 아닌 정수 $x_{i,i+1}, x_{i,i+2}, \ldots, x_{i,n}$이 공백 하나로 구분되어 주어진다. $x_{i,j}$는 역 $i$에서 타 역 $j$에서 내리는 승객의 수이다. 전체 승객 수(모든 $x_{i,j}$의 합)는 $2\,000\,000\,000$을 넘지 않는다.

Byteasar가 $k$번의 검표 구간을 가장 잘 골랐을 때 검표할 수 있는 서로 다른 승객 수의 최댓값을 한 줄에 정수 하나로 출력한다.

역이 $7$개이고 검표를 $2$번 하는 경우, 역 $2$와 역 $5$를 출발한 직후에 검표하면 전체 $52$명 중 $42$명을 검표할 수 있고, 이것이 최댓값이다.