The Triangle

Farmer John has given Bessie a triangular grid with $N$ rows ($1 \le N \le 700$). Row $i$ contains $i$ integers; the $j$-th integer of row $i$ is $v_{i,j}$ ($-10^9 \le v_{i,j} \le 10^9$, $1 \le j \le i$).

Bessie must choose a sub-triangle whose side length is at least $K$ ($1 \le K \le 20$, $K \le N$). A sub-triangle is again a triangular block of the grid. It may point the same way as the whole grid (a single top cell that widens by one cell per row going down), or it may be upside down (a full top row that narrows by one cell per row until it ends in a single bottom cell). A sub-triangle of side length $s$ contains $s(s+1)/2$ cells.

For the example grid with $N = 3$

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

the two orientations of a side-2 sub-triangle look like this (upward on the left, upside down on the right).

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

Farmer John takes the average of all numbers in the chosen sub-triangle, discards the digits after the decimal point (truncating toward zero, so the value keeps its sign), and gives Bessie that many gold coins — or takes that many away if the value is negative.

For instance, with $K = 2$ the best sub-triangle of the grid above has average $(4 + 6 - 3)/3 = 2.333\ldots$, which truncates to $2$.

Help Bessie find the maximum number of coins she can obtain over all valid sub-triangles.

• Line 1: two space-separated integers $N$ and $K$.
• Lines 2 to $N+1$: line $i+1$ contains $i$ space-separated integers $v_{i,1}, v_{i,2}, \ldots, v_{i,i}$.

• A single line containing the maximum number of coins Bessie can obtain. This value may be negative (the smallest loss she can guarantee).