K-Matrix_第十八届浙大城市学院程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

You are given a matrix $a_{}$ consists of $n_{}$ rows and $m_{}$ columns. We call the grid in the upper left corner as $(1, 1)_{}$ and call the grid in the bottom right corner as $(n, m)_{}$ . Each grid contains an integer $a_{ij}$ .
You can choose at most $k_{}$ grids. In addition, all grids $(i,j)(i\leq x,j\leq y)_{}$ except $(x,y)_{}$ should be chosen before you choose $(x,y)_{}$ . For example, if you want to choose $(2,2)_{}$ , you should choose $(1,1),(1,2),(2,1)_{}$ previously.
Your point is the sum of integers in the chosen grids, please calculate the maximum point you can get.

输入描述:

The first line contains three integers  —  denote the number of rows and columns of the matrix, and  denote the number of grids you can choose mostly.
Then  lines follow, each line contains  integers  .

输出描述:

Output an integer representing the maximum point you can get.

示例1

输入

复制

输出

复制

说明

In the example, the following steps are a possible option that can get the maximum point.
In move  , you can only choose  , and you choose  .
In move  , you can choose  or  , and you choose  
In move  , you can choose  or  , and you choose  
In move  , you can choose  or  or  , and you choose  
So you can get  points.