삼각형: 자료 구조

평행 우주에서는 컴퓨터 과학에서 가장 중요한 자료 구조가 삼각형이다. 크기가 $M$인 삼각형은 $M$개의 행으로 이루어지며, $i$번째 행에는 $i$개의 원소가 있다. 행들은 정삼각형 모양을 이루고, 각 행은 삼각형의 가운데를 지나는 수직 대칭선을 중심으로 정렬된다. 예를 들어 아래 그림은 크기가 4인 삼각형이다.

삼각형 안에는 부분 삼각형이 포함된다. 예를 들어 위의 삼각형에는 크기가 1인 부분 삼각형이 10개 있고, 크기가 2인 부분 삼각형이 6개 있다. 크기가 2인 부분 삼각형 중 두 개는 (3,1,2)를 포함하는 삼각형과 (4,6,1)을 포함하는 삼각형이다. 위의 삼각형에는 크기가 3인 부분 삼각형도 3개 있으며, 그중 하나는 (2,2,1,1,4,2)를 포함한다. 모든 삼각형은 자기 자신의 부분 삼각형이다.

크기가 $N$인 삼각형이 주어진다. 크기가 $K$인 모든 부분 삼각형의 최댓값의 합을 구하시오.

첫째 줄에 공백으로 구분된 두 정수 $N$과 $K$가 주어진다 ($1 \le K \le N \le 3000$). 이어서 $N$개의 줄에 삼각형이 주어진다. $i$번째 줄에는 $i$번째 행의 원소인 정수 $a_{i,1}, a_{i,2}, \ldots, a_{i,i}$가 공백으로 구분되어 주어진다. 모든 값은 $0 \le a_{i,j} \le 10^9$을 만족한다. 배점 15점 중 4점은 $N \le 1000$인 경우이다.

크기가 $K$인 모든 부분 삼각형의 최댓값의 합을 정수로 출력한다.