Description

Xiaoxin is playing a simple computer game.

In the game, there is a circular road with $n$ robot factories. Between every pair of adjacent robot factories, there is a short segment of road. Starting from some factory, Xiaoxin numbers the $n$ robot factories in clockwise order as $1 \sim n$. Since the road is circular, factory $n$ and factory $1$ are connected by a segment of road. Xiaoxin also numbers the $n$ road segments as $1 \sim n$, and stipulates that segment $i$ connects factory $i$ and factory $i+1$ ($1 \le i \le n-1$), while segment $n$ connects factory $n$ and factory $1$.

During the game, in each time unit, every road segment will spawn some coins, and the number of coins changes over time; that is, the number of coins on the same road segment may differ between time units. Xiaoxin needs a robot’s help to collect the coins on the road. A robot must be purchased at a robot factory using some coins. Once purchased, the robot will walk along the circular road clockwise, moving once per time unit: in each time unit it moves from its current factory to the next factory and collects all coins on the road segment it traverses for Xiaoxin. For example, if Xiaoxin buys a robot at factory $i$ ($1 \le i \le n$), then starting from factory $i$, the robot walks clockwise. On its first move, it traverses segment $i$, reaches factory $i+1$ (if $i=n$, it reaches factory $1$), and collects all coins on segment $i$.

At no time may there be $2$ or more robots on the road simultaneously, and each robot can walk at most $p$ times. When buying a robot, Xiaoxin must also set its number of moves, which can be any integer from $1$ to $p$. After finishing its assigned number of moves, the robot disappears automatically, and Xiaoxin must immediately buy a new robot at any factory and set its number of moves.

Additional notes:

1. Time starts when Xiaoxin buys a robot for the first time.
2. Buying a robot and setting its number of moves are instantaneous and take no time.
3. Buying a robot and a robot’s walking are independent processes. You cannot buy a robot while another robot is moving; a robot starts moving only after it has been bought and its number of moves has been set.
4. The purchase cost at the same factory is always the same, but the costs at different factories may differ.
5. All robot purchase costs are deducted from the coins collected at the end of the game. Therefore, during the game, Xiaoxin never fails to proceed due to insufficient coins. Because of this, the final collected coins may be negative.

You are given, for every road segment and every time unit, the number of coins that appear, as well as the purchase cost at each robot factory. Please tell Xiaoxin the maximum number of coins he can collect after $m$ time units, after subtracting all robot purchase costs.

Input Format

The first line contains $3$ positive integers $n, m, p$, as described above.

The next $n$ lines each contain $m$ positive integers separated by single spaces. The $i$-th line describes the number of coins that appear on segment $i$ in each time unit ($1 \le$ coin count $\le 100$). That is, the $j$-th ($1 \le j \le m$) number on the $i$-th line is the number of coins that appear on segment $i$ in the $j$-th time unit.

The last line contains $n$ integers separated by single spaces. The $i$-th number is the number of coins required to buy a robot at factory $i$ ($1 \le$ coin count $\le 100$).

Output Format

Output a single line with $1$ integer: the maximum number of coins Xiaoxin can collect in $m$ time units after subtracting all robot purchase costs.

2 3 2 
1 2 3 
2 3 4 
1 2

5

Hint

• For $40\%$ of the testdata: $2 \le n \le 40$, $1 \le m \le 40$.
• For $90\%$ of the testdata: $2 \le n \le 200$, $1 \le m \le 200$.
• For $100\%$ of the testdata: $2 \le n \le 1000$, $1 \le m \le 1000$, $1 \le p \le m$.

NOIP 2009 Junior Problem 4.

Translated by ChatGPT 5