Maximizing Triangular Subgrid Average

Bessie is given an isosceles triangular grid with n rows. The i-th row contains i integers, and the values can be as large as \( -10^9 \) or as small as \( 10^9 \). She is allowed to choose any contiguous sub‐triangle whose side length is at least \(K\) and at most \(2K\) (note that \(K \le n\)). The chosen sub‐triangle can be oriented in the same way as the original triangle (with the smaller rows at the top) or upside down (with the smaller rows at the bottom).

Once Bessie chooses her sub‐triangle, Farmer John will compute the average of all numbers in that sub‐triangle, discarding any fractional part (i.e. performing a truncation toward zero), and then give her that many gold coins (or take that many coins if the number is negative). Bessie wants to maximize her prize (or minimize her loss) by choosing the sub–triangle with the maximum truncated average. Help her determine the maximum amount of coins she can receive.

Note: For a sub–triangle with side length \(L\), the number of elements is \(\frac{L(L+1)}{2}\), and the average is defined as \(\text{avg}=\frac{\text{sum of elements}}{\frac{L(L+1)}{2}}\). When converting to an integer, simply discard the digits to the right of the decimal point.

Example:

Input:
3 2
5
-8 4
2 -3 6
The triangular grid:
5
-8   4
2  -3   6
One optimal sub–triangle is:
5
-8   4
2  -3   6
with the selected numbers being 4, 6, and -3 whose average is (\frac{4+6-3}{3}\approx2.333...), which truncates to 2.
Output:
2

inputFormat

The first line contains two integers, n and K (with \(1 \le n \le 700\) and \(1 \le K \le 20, K \le n\)). The following n lines describe the triangle. The i-th line contains exactly i integers, representing the values in the i-th row of the triangle.

outputFormat

Output a single integer, the maximum truncated average Bessie can achieve by selecting an appropriate sub–triangle.

sample

3 2
5
-8 4
2 -3 6

2