삼각형

Farmer John이 Bessie에게 $N$개의 행으로 이루어진 삼각형 격자를 주었다 ($1 \le N \le 700$). $i$번째 행에는 $i$개의 정수가 있으며, $i$번째 행의 $j$번째 정수를 $v_{i,j}$라 한다 ($-10^9 \le v_{i,j} \le 10^9$, $1 \le j \le i$).

Bessie는 한 변의 길이가 $K$ 이상인 부분 삼각형을 하나 고른다 ($1 \le K \le 20$, $K \le N$). 부분 삼각형 역시 격자 안의 삼각형 모양 영역이며, 전체 격자와 같은 방향(하나의 꼭대기 칸에서 아래로 내려갈수록 한 칸씩 넓어지는 형태)일 수도 있고, 위아래가 뒤집힌 방향(맨 윗줄이 가장 넓고 아래로 갈수록 한 칸씩 좁아져 마지막에 한 칸으로 끝나는 형태)일 수도 있다. 한 변의 길이가 $s$인 부분 삼각형은 $s(s+1)/2$개의 칸을 포함한다.

$N = 3$인 예시 격자

    / \
   / 5 \
  /-8  4\
 / 2 -3 6\
 ---------

에서 한 변의 길이가 2인 부분 삼각형은 다음 두 방향으로 놓일 수 있다 (왼쪽이 정방향, 오른쪽이 뒤집힌 방향).

   / 5 \           -8  4
  /-8  4\           \-3/
                     \/

Farmer John은 고른 부분 삼각형에 있는 모든 수의 평균을 구한 뒤 소수점 아래 자리를 버리고(0 방향으로 버림하므로 부호는 그대로 유지된다) 그 값만큼 금화를 준다. 값이 음수이면 그만큼 금화를 가져간다.

예를 들어 $K = 2$일 때 위 격자에서 가장 좋은 부분 삼각형의 평균은 $(4 + 6 - 3)/3 = 2.333\ldots$이고, 소수점 아래를 버리면 $2$가 된다.

가능한 모든 부분 삼각형 중에서 Bessie가 얻을 수 있는 금화의 최댓값을 구하여라.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $K$.
• 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄에는 $i$개의 정수 $v_{i,1}, v_{i,2}, \ldots, v_{i,i}$가 공백으로 구분되어 주어진다.

• Bessie가 얻을 수 있는 금화의 최댓값을 한 줄에 출력한다. 이 값은 음수일 수 있다(손실을 최소화한 값).