{"raw_statement":[{"iden":"statement","content":"You own a company that organizes tours to Mount Fuji everyday. \n\nEach 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.\n\nPeople 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.\n\nNote 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.\n\nFor 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$.\n\nThe first line of input contains a single integer $T$ ($1 <= T <= 250$), the number of test cases.\n\nThe first line of each test case contains three space-separated integers $m$, $n$, and $R$ ($1 <= m times n <= 10^5$) ($1 <= R <= 10^5$), the number of stations, the number of days, and the capacity of a single bus, respectively.\n\nEach of the following $m$ lines contains $n$ integers, where $a_{i , j}$ ($1 <= a_{i , j} <= 10^5$) represents the number of people who booked a ticket to get in the $j^(t h)$ tour from the $i^(t h)$ station.\n\nThe total sum of $A_{i , j} <= 5 * 10^5$\n\nFor each test case, output a single line with the minimum number of buses needed to satisfy all the tours.\n\n"},{"iden":"input","content":"The first line of input contains a single integer $T$ ($1 <= T <= 250$), the number of test cases.The first line of each test case contains three space-separated integers $m$, $n$, and $R$ ($1 <= m times n <= 10^5$) ($1 <= R <= 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 <= a_{i , j} <= 10^5$) represents the number of people who booked a ticket to get in the $j^(t h)$ tour from the $i^(t h)$ station.The total sum of $A_{i , j} <= 5 * 10^5$"},{"iden":"output","content":"For each test case, output a single line with the minimum number of buses needed to satisfy all the tours."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ m \\in \\mathbb{Z}^+ $ be the number of stations, $ n \\in \\mathbb{Z}^+ $ the number of days, and $ R \\in \\mathbb{Z}^+ $ the capacity of a single bus.  \nLet $ A = (a_{i,j}) \\in \\mathbb{Z}^{m \\times n} $, where $ a_{i,j} $ is the number of people booking tour $ j $ from station $ i $.  \n\nLet $ b_{i,j} \\in \\mathbb{Z}_{\\geq 0} $ denote the number of buses stationed at station $ i $ on day $ j $.  \nLet $ x_{i,j,k} \\in \\{0,1\\} $ denote whether a bus is relocated from station $ i $ on day $ j $ to station $ k $ on day $ j+2 $ (for $ j \\leq n-2 $).  \n\n**Constraints**  \n1. For each station $ i \\in \\{1, \\dots, m\\} $ and day $ j \\in \\{1, \\dots, n\\} $:  \n   $$\n   b_{i,j} \\cdot R \\geq a_{i,j}\n   $$  \n2. Bus conservation per station and day:  \n   For each station $ i \\in \\{1, \\dots, m\\} $ and day $ j \\in \\{1, \\dots, n\\} $:  \n   $$\n   b_{i,j} = \\sum_{k=1}^m x_{k,j-2,i} + \\sum_{k=1}^m x_{i,j-1,k}^{\\text{stay}} + \\delta_{j,1} \\cdot b_{i,1}^{\\text{initial}}\n   $$  \n   (where $ x_{k,j-2,i} = 0 $ if $ j-2 < 1 $, and $ \\text{stay} $ means the bus was not relocated from station $ i $ on day $ j-1 $)  \n3. Relocation constraint:  \n   For each station $ i \\in \\{1, \\dots, m\\} $ and day $ j \\in \\{1, \\dots, n-2\\} $:  \n   $$\n   \\sum_{k=1}^m x_{i,j,k} \\leq b_{i,j}\n   $$  \n   (only buses present at station $ i $ on day $ j $ can be relocated)  \n4. Each bus relocation takes one day: a bus used at station $ i $ on day $ j $ can only appear at station $ k $ on day $ j+2 $.  \n\n**Objective**  \nMinimize the total number of buses:  \n$$\n\\min \\sum_{i=1}^m \\sum_{j=1}^n b_{i,j} - \\sum_{i=1}^m \\sum_{j=2}^{n-1} \\sum_{k=1}^m x_{i,j,k}\n$$  \n*(Note: buses are counted only once when first deployed; relocation does not add new buses.)*  \n\nAlternatively, since buses are reusable and relocation doesn't consume them, the objective reduces to:  \n$$\n\\min \\sum_{i=1}^m \\sum_{j=1}^n b_{i,j} \\quad \\text{subject to constraints above}\n$$  \nwith the understanding that $ b_{i,j} $ represent *active* buses at station $ i $ on day $ j $, and relocation flows are constrained to preserve bus count across time.  \n\n**Note**: The problem reduces to a dynamic flow problem over time and stations, where each day’s demand must be met by buses either present from prior days or newly deployed, with a 2-day delay for inter-station movement.","simple_statement":"You have m stations and n days. Each day, each station has a number of people wanting to go on a tour. Each bus can carry R people. You need to assign buses to stations each day so that all people are transported. Buses can be moved between stations, but moving a bus takes a full day (it can’t be used on the day it moves). Find the minimum total number of buses needed.","has_page_source":false}