There are \(N\) arrays, each array has \(M\) positive integer elements The \(j\)-th element of the \(i\)-th array is \(A_{i,j}\).
Initially, Chaneka's digital wallet contains \(0\) money. Given an integer \(K\). Chaneka will do \(M-K+1\) operations. In the \(p\)-th operation, Chaneka does the following procedure:
- Choose any array. Let's say Chaneka chooses the \(x\)-th array.
- Choose an index \(y\) in that array such that \(p \leq y \leq p+K-1\).
- Add the value of \(A_{x, y}\) to the total money in the wallet.
- Change the value of \(A_{x, y}\) into \(0\).
Determine the maximum total money that can be earned!
Output
Output an integer representing the maximum total money that can be earned.
Note
In the first example, the following is a sequence of operations of one optimal strategy:
- Choosing element \(A_{1, 1}\) with a value of \(10\).
- Choosing element \(A_{3, 2}\) with a value of \(8\).
- Choosing element \(A_{2, 3}\) with a value of \(9\).
So the total money earned is \(10+8+9=27\).
In the second example, the following is a sequence of operations of one optimal strategy:
- Choosing element \(A_{3, 2}\) with a value of \(8\).
- Choosing element \(A_{1, 2}\) with a value of \(9\).
So the total money earned is \(8+9=17\).
In the third example, the following is a sequence of operations of one optimal strategy:
- Choosing element \(A_{1, 3}\) with a value of \(10\).
- Choosing element \(A_{1, 2}\) with a value of \(9\).
So the total money earned is \(10+9=19\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 1
10 4 2
8 1 9
4 8 2
|
27
|
|
2
|
3 3 2
5 9 4
1 3 1
2 8 7
|
17
|
|
3
|
3 4 3
5 9 10 1
1 3 1 5
2 5 7 2
|
19
|