Optimal Boat Dispatch Revenue

Arthur has n tasks that need to be completed. For each task, he must dispatch between 1 and m boats (dispatching zero boats is not allowed). Dispatching one boat for a task costs k yuan. For the i-th task, dispatching j boats will yield a reward of \(a_{i,j}\) yuan.

The net gain from dispatching j boats for the i-th task is given by:

[ \text{Net gain}{i,j} = a{i,j} - j \times k ]

For each task, Arthur can choose the number of boats to dispatch to maximize his net gain. The tasks are independent so the optimal overall revenue is the sum of the maximum net gains from each task.

Note that the optimal total revenue might be negative.

inputFormat

The first line contains three integers n, m and k (1 ≤ n, m ≤ 10⁵, k is an integer). Each of the next n lines contains m space-separated integers: \(a_{i,1}, a_{i,2}, \ldots, a_{i,m}\), where \(a_{i,j}\) represents the reward for dispatching j boats for the i-th task.

outputFormat

Output a single integer, the maximum total revenue Arthur can achieve by optimally dispatching boats for all tasks.

sample

1 3 2
3 5 8

2