En un universo paralelo, la estructura de datos más importante en informática es el triángulo. Un el triángulo de tamaño M consiste en M filas, con la i-ésima fila que contiene i elementos. Además, estas filas deben estar organizadas en forma de triángulo equilátero. Es decir, cada fila está centrada alrededor de una línea vertical de simetría a través del centro del triángulo. Por ejemplo, el diagrama a continuación muestra un triángulo de tamaño 4:

Un triángulo contiene sub-triángulos. Por ejemplo, el triángulo anterior contiene diez sub-triángulos de tamaño 1, seis sub-triángulos de tamaño 2 (dos de los cuales son el triángulo que contiene (3, 1, 2) y el triángulo que contiene (4, 6, 1)), tres sub-triángulos de tamaño 3 (uno de los cuales contiene (2, 2, 1, 1, 4, 2)).

Nota que cada triángulo es un sub-triángulo de sí mismo.

Te dan un triángulo de tamaño N y debes encontrar la suma de los elementos máximos de cada sub-triángulo de tamaño K.

Especificación de entrada

La primera línea contiene dos enteros separados por espacios N y K ~(1 \leq K \leq N \leq 3000)~. A continuación hay N líneas que describen el triángulo. La i-ésima de estas líneas contiene i enteros ~a_i,j~ separados por espacio, ~j(0 \leq a_i,j \leq 10^9)~, que representan la i-ésima fila del triángulo.

Especificación de salida

Muestra la suma entera de los elementos máximos de cada sub-triángulo de tamaño K.

Ejemplo de entrada

4 2
3
1 2
4 2 1
6 1 4 2

Ejemplo de salida

23