RoAlgo Contest #5 - Back to School Edition | suporter

XB has decided to become a football fan and started watching Liga 1. To enjoy as many successes as possible, he created his own championship with $n$ teams and $m$ stages, knowing for each team $i$ how many points they get in each stage $j$, denoted as $scor_{ij}$.

However, XB is a result-oriented supporter, and although loyalty should mean more in football, he cannot conceive staying with the same team even during tough times, so he can change his favorite team at most $k$ times during a season (he understands loyalty somewhat, just not entirely).

Task

The goal is to enjoy as many points as possible from his favorite teams throughout the season, knowing that he can change his favorite team at most $k$ times. If in a stage $j$ he supports team $i$, the score he enjoys will increase by $scor_{ij}$. Determine this maximum score.

Input Data

On the first line, there are three natural numbers, $n$, $m$, and $k$, representing the number of teams, the number of stages, and the maximum number of favorite team changes.

On the next $n$ lines, there are $m$ natural numbers, $scor_{ij}$ representing the score obtained by team $i$ in stage $j$.

Output Data

On the first line, there will be a single number, the maximum score XB can achieve if he supports the right teams.

Constraints and Clarifications

• $1 \leq n, m, k \leq 300$
• $0 \leq scor_{ij} \leq 5$

Example

stdin

4 5 1
3 2 4 5 1
1 1 5 5 5
2 4 1 2 3
4 5 2 1 3

stdout

24

Explanation

XB can first support team $4$ for two rounds, and then he will support team $2$, thus obtaining $4 + 5 + 5 + 5 + 5 = 24$ points.