405473: GYM101968 I Tours

You own a company that organizes tours to Mount Fuji everyday.

Each day, a number of buses stationed at different cities pick up people in the morning and get them back to the station in the evening after the tour has ended.

People have already booked their tickets for the next $$$n$$$ days, so you want to plan the number of buses that you want to put at each station such that there's always enough buses for the people attending the tour from each station, and the total number of buses used is minimum possible.

Note that you can make any bus go from one station to another between multiple days, but doing so requires a whole day for the bus to relocate to the other station, so you can't use it during that day in any station.

For example, if a bus was used at station $$$x$$$ at day $$$k$$$, and we need it to relocate to station $$$y$$$, then it will only arrive and be usable there on day $$$k+2$$$.

The first line of input contains a single integer $$$T$$$ ($$$1 \le T \le 250$$$), the number of test cases.

The first line of each test case contains three space-separated integers $$$m$$$, $$$n$$$, and $$$R$$$ ($$$1 \le m \times n \le 10^5$$$) ($$$1 \le R \le 10^5$$$), the number of stations, the number of days, and the capacity of a single bus, respectively.

Each of the following $$$m$$$ lines contains $$$n$$$ integers, where $$$a_{i,j}$$$ ($$$1 \le a_{i,j} \le 10^5$$$) represents the number of people who booked a ticket to get in the $$$j^{th}$$$ tour from the $$$i^{th}$$$ station.

The total sum of $$$ A_{i,j} \le 5*10^5$$$

For each test case, output a single line with the minimum number of buses needed to satisfy all the tours.

2
2 3 1
1 0 2
1 0 0
1 5 1
1 2 8 1 6

2
8