Collecting Gold on a Circular Road

In this problem, you are given a circular road with n robotic factories and n connecting roads. The factories are numbered from \(1\) to \(n\) in clockwise order starting from an arbitrary factory, and similarly, the roads are numbered \(1\) to \(n\) such that road \(i\) connects factory \(i\) and factory \(i+1\) for \(1 \le i \le n-1\) while road \(n\) connects factory \(n\) and factory \(1\).

The game proceeds in discrete time units and starts when a robot is first purchased. At each unit time, every road produces some coins. However, the coin production on a road may vary at different time units. In order to collect coins, you need to purchase a robot at some factory. When you purchase a robot at factory \(i\) (incurring a cost of \(c_i\) coins), you immediately assign it a number of moves \(t\) (an integer between \(1\) and \(p\)). The robot then starts moving in the clockwise direction. Specifically, if you purchase the robot at factory \(i\), then on its first move it will travel along road \(i\) (collecting all coins on that road at that time unit), on its second move it will travel along road \(i+1\) (or road \(1\) if \(i = n\)), and so on.

After a robot has completed its \(t\) moves, it disappears and you immediately purchase another robot (at any factory of your choice) and assign it a new move count in the range \([1, p]\). Note that the robot movements and robot purchases do not overlap in time: the coin collection for a robot during its moves happens at consecutive time units, and the purchase itself is instantaneous and does not consume time.

You are given:

• \(n\): the number of factories (and roads),
• \(m\): the total number of time units,
• \(p\): the maximum number of moves a robot can be instructed to perform,
• An array \(c\) of length \(n\) where \(c_i\) is the cost of purchasing a robot at factory \(i\),
• An \(n \times m\) matrix \(A\) where \(A_{i,j}\) is the number of coins that appear on road \(i\) during time unit \(j\) (1-indexed).

Your task is to determine the maximum number of coins that can be collected after \(m\) time units, net of the purchasing costs. Formally, you need to partition the \(m\) time units into segments. For each segment starting at global time \(L+1\) with length \(t\) (\(1 \le t \le p\)) and choosing a starting factory \(i\), the robot collects coins as follows:

[ \text{Profit} = \left( \sum_{r=1}^{t} A_{(i+r-1) \bmod n,, L+r} \right) - c_i ]

The answer is the maximum total profit you can achieve by choosing an optimal segmentation and purchasing strategy.

inputFormat

The input consists of:

1. A line containing three integers \(n\), \(m\), and \(p\) (the number of factories/roads, the number of time units, and the maximum moves per robot, respectively).
2. A line containing \(n\) integers: \(c_1, c_2, \ldots, c_n\), where \(c_i\) is the cost to purchase a robot at factory \(i\).
3. Then \(n\) lines follow. The \(i\)-th of these lines contains \(m\) integers: \(A_{i,1}, A_{i,2}, \ldots, A_{i,m}\), where \(A_{i,j}\) represents the coins produced on road \(i\) at time unit \(j\).

outputFormat

Output a single integer: the maximum net coins that can be collected after \(m\) time units (i.e. total collected coins minus the total cost for purchasing robots).

sample

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

10