Maximum Collected Sum on K Paths in a Matrix

Given an n \times n matrix where each cell contains a non-negative integer \(A_{i,j}\) (with \(A_{i,j} \le 10^3\)), you are to perform \(K\) journeys starting from the top‐left cell \((1,1)\) to the bottom‐right cell \((n,n)\). In each journey, you can only move either right or down. When you step onto a cell, you collect its value and then that cell’s value becomes \(0\); note that a cell’s value can only be collected once even if it is visited in multiple journeys.

Your task is to choose \(K\) paths so that the total sum of the collected numbers is maximized.

Hint: Although paths may overlap, overlapping cells yield a benefit only the first time they are visited.

inputFormat

The first line contains two integers \(n\) and \(K\).

Each of the next \(n\) lines contains \(n\) integers, representing the matrix.

outputFormat

Output a single integer: the maximum total sum of numbers that can be collected over \(K\) journeys.

sample

3 2
1 2 3
4 5 6
7 8 9

42