Canadian Computing Competition: 2019 Stage 1, Senior #5

In a parallel universe, the most important data structure in computer science is the triangle. A triangle of size \(M\) consists of \(M\) rows, with the \(i^{th}\) row containing \(i\) elements. Furthermore, these rows must be arranged to form the shape of an equilateral triangle. That is, each row is centred around a vertical line of symmetry through the middle of the triangle. For example, the diagram below shows a triangle of size 4:

A triangle contains sub-triangles. For example, the triangle above contains ten sub-triangles of size 1, six sub-triangles of size 2 (two of which are the triangle containing \((3,1,2)\) and the triangle containing \((4,6,1)\) ), three sub-triangles of size 3 (one of which contains \((2,2,1,1,4,2)\) ). Note that every triangle is a sub-triangle of itself.

You are given a triangle of size \(N\) and must find the sum of the maximum elements of every sub-triangle of size \(K\) .

Input Specification

The first line contains two space-separated integers \(N\) and \(K\) ( \(1 \le K \le N \le 3\,000\) ).

Following this are \(N\) lines describing the triangle. The \(i^{th}\) of these lines contains \(i\) space-separated integers \(a_{i,j}\) ( \(0 \le a_{i,j} \le 10^9\) ), representing the \(i^{th}\) row of the triangle.

For 4 of the 15 available marks, \(N \le 1000\) .

Output Specification

Output the integer sum of the maximum elements of every sub-triangle of size \(K\) .

Sample Input

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

Output for Sample Input

23