{"problem":{"name":"E. Mini Metro","description":{"content":"In a simplified version of a \"Mini Metro\" game, there is only one subway line, and all the trains go in the same direction. There are $n$ stations on the line, $a_i$ people are waiting for the train a","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1007E"},"statements":[{"statement_type":"Markdown","content":"In a simplified version of a \"Mini Metro\" game, there is only one subway line, and all the trains go in the same direction. There are $n$ stations on the line, $a_i$ people are waiting for the train at the $i$\\-th station at the beginning of the game. The game starts at the beginning of the $0$\\-th hour. At the end of each hour (couple minutes before the end of the hour), $b_i$ people instantly arrive to the $i$\\-th station. If at some moment, the number of people at the $i$\\-th station is larger than $c_i$, you lose.\n\nA player has several trains which he can appoint to some hours. The capacity of each train is $k$ passengers. In the middle of the appointed hour, the train goes from the $1$\\-st to the $n$\\-th station, taking as many people at each station as it can accommodate. A train can not take people from the $i$\\-th station if there are people at the $i-1$\\-th station.\n\nIf multiple trains are appointed to the same hour, their capacities are being added up and they are moving together.\n\nThe player wants to stay in the game for $t$ hours. Determine the minimum number of trains he will need for it.\n\n## Input\n\nThe first line contains three integers $n$, $t$, and $k$ ($1 \\leq n, t \\leq 200, 1 \\leq k \\leq 10^9$) — the number of stations on the line, hours we want to survive, and capacity of each train respectively.\n\nEach of the next $n$ lines contains three integers $a_i$, $b_i$, and $c_i$ ($0 \\leq a_i, b_i \\leq c_i \\leq 10^9$) — number of people at the $i$\\-th station in the beginning of the game, number of people arriving to $i$\\-th station in the end of each hour and maximum number of people at the $i$\\-th station allowed respectively.\n\n## Output\n\nOutput a single integer number — the answer to the problem.\n\n[samples]\n\n## Note\n\n![image](https://espresso.codeforces.com/ab72e1f01c4f5155e126b82d6150e57411191165.png)\n\nLet's look at the sample. There are three stations, on the first, there are initially 2 people, 3 people on the second, and 4 people on the third. Maximal capacities of the stations are 10, 9, and 8 respectively.\n\nOne of the winning strategies is to appoint two trains to the first and the third hours. Then on the first hour, the train takes all of the people from the stations, and at the end of the hour, 4 people arrive at the first station, 3 on the second, and 2 on the third.\n\nIn the second hour there are no trains appointed, and at the end of it, the same amount of people are arriving again.\n\nIn the third hour, the train first takes 8 people from the first station, and when it arrives at the second station, it takes only 2 people because it can accommodate no more than 10 people. Then it passes by the third station because it is already full. After it, people arrive at the stations once more, and the game ends.\n\nAs there was no such moment when the number of people at a station exceeded maximal capacity, we won using two trains.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在简化版的《迷你地铁》游戏中，只有一条地铁线路，所有列车都朝同一方向行驶。线路上有 $n$ 个车站，游戏开始时第 $i$ 个车站有 $a_i$ 人等待。游戏从第 $0$ 小时开始。在每小时结束时（即将结束前的几分钟），$b_i$ 人会立即到达第 $i$ 个车站。如果在某一时刻，第 $i$ 个车站的人数超过了 $c_i$，则你输掉游戏。\n\n玩家可以将若干列车分配到某些小时。每列列车的容量为 $k$ 名乘客。在分配的小时的中间，列车从第 $1$ 站行驶到第 $n$ 站，在每个车站尽可能多地搭载乘客。如果第 $i-1$ 个车站还有乘客，则列车不能从第 $i$ 个车站搭载乘客。\n\n如果多个列车被分配到同一小时，它们的容量会相加，且会一起行驶。\n\n玩家希望坚持游戏 $t$ 小时。请确定他至少需要多少列列车。\n\n第一行包含三个整数 $n$、$t$ 和 $k$（$1 \\leq n, t \\leq 200$，$1 \\leq k \\leq 10^9$）——分别表示线路上的车站数、希望存活的小时数以及每列列车的容量。\n\n接下来的 $n$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $c_i$（$0 \\leq a_i, b_i \\leq c_i \\leq 10^9$）——分别表示游戏开始时第 $i$ 个车站的人数、每小时结束时到达第 $i$ 个车站的人数，以及第 $i$ 个车站允许的最大人数。\n\n请输出一个整数——问题的答案。\n\n让我们看一个样例。有三个车站，第一个车站初始有 2 人，第二个车站有 3 人，第三个车站有 4 人。各车站的最大容量分别为 10、9 和 8。\n\n一种获胜策略是将两列列车分别分配到第 1 小时和第 3 小时。在第 1 小时，列车从所有车站接走所有乘客，小时结束时，第一个车站到达 4 人，第二个车站到达 3 人，第三个车站到达 2 人。\n\n在第 2 小时没有分配列车，小时结束时，同样数量的人再次到达。\n\n在第 3 小时，列车首先从第一个车站接走 8 人，当到达第二个车站时，由于列车容量最多为 10 人，只能再接走 2 人。然后列车经过第三个车站，因为此时它已满。之后，乘客再次到达各车站，游戏结束。\n\n由于没有任何时刻车站人数超过最大容量，我们使用两列列车获胜。\n\n## Input\n\n第一行包含三个整数 $n$、$t$ 和 $k$（$1 \\leq n, t \\leq 200$，$1 \\leq k \\leq 10^9$）——分别表示线路上的车站数、希望存活的小时数以及每列列车的容量。接下来的 $n$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $c_i$（$0 \\leq a_i, b_i \\leq c_i \\leq 10^9$）——分别表示游戏开始时第 $i$ 个车站的人数、每小时结束时到达第 $i$ 个车站的人数，以及第 $i$ 个车站允许的最大人数。\n\n## Output\n\n请输出一个整数——问题的答案。\n\n[samples]\n\n## Note\n\n让我们看一个样例。有三个车站，第一个车站初始有 2 人，第二个车站有 3 人，第三个车站有 4 人。各车站的最大容量分别为 10、9 和 8。\n\n一种获胜策略是将两列列车分别分配到第 1 小时和第 3 小时。在第 1 小时，列车从所有车站接走所有乘客，小时结束时，第一个车站到达 4 人，第二个车站到达 3 人，第三个车站到达 2 人。\n\n在第 2 小时没有分配列车，小时结束时，同样数量的人再次到达。\n\n在第 3 小时，列车首先从第一个车站接走 8 人，当到达第二个车站时，由于列车容量最多为 10 人，只能再接走 2 人。然后列车经过第三个车站，因为此时它已满。之后，乘客再次到达各车站，游戏结束。\n\n由于没有任何时刻车站人数超过最大容量，我们使用两列列车获胜。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, t, k \\in \\mathbb{Z}^+ $ denote the number of stations, target hours to survive, and train capacity, respectively.  \nFor each station $ i \\in \\{1, \\dots, n\\} $:  \n- $ a_i \\in \\mathbb{Z}_{\\geq 0} $: initial number of passengers.  \n- $ b_i \\in \\mathbb{Z}_{\\geq 0} $: number of new passengers arriving at the end of each hour.  \n- $ c_i \\in \\mathbb{Z}_{>0} $: maximum allowed passengers at station $ i $ (capacity constraint).  \n\nLet $ x_h \\in \\mathbb{Z}_{\\geq 0} $ denote the number of trains dispatched at the **middle of hour** $ h \\in \\{0, 1, \\dots, t-1\\} $.  \nTotal trains used: $ \\sum_{h=0}^{t-1} x_h $.  \n\nLet $ p_{i,h} \\in \\mathbb{Z}_{\\geq 0} $ denote the number of passengers at station $ i $ **just before** the train in hour $ h $ arrives (if any), for $ h \\in \\{0, \\dots, t-1\\} $, and $ p_{i,t} $ the number after the final hour (no train after hour $ t-1 $).\n\n---\n\n**Constraints**  \n\n1. **Initial state**:  \n   $$\n   p_{i,0} = a_i \\quad \\forall i \\in \\{1, \\dots, n\\}\n   $$\n\n2. **Passenger accumulation (end of hour)**:  \n   For each hour $ h \\in \\{0, \\dots, t-1\\} $, after the train at hour $ h $ departs (if any), and before the next hour:  \n   $$\n   p_{i,h+1} = \\max\\left(0, p_{i,h} - \\text{taken}_{i,h}\\right) + b_i\n   $$\n   where $ \\text{taken}_{i,h} $ is the number of passengers picked up at station $ i $ during hour $ h $, defined below.\n\n3. **Train pickup rule (sequential, left-to-right)**:  \n   Let $ C_h = x_h \\cdot k $ be the total capacity of all trains in hour $ h $.  \n   For station $ i $, define:  \n   $$\n   \\text{taken}_{i,h} = \\min\\left(p_{i,h}, \\max\\left(0, C_h - \\sum_{j=1}^{i-1} \\text{taken}_{j,h}\\right)\\right)\n   $$\n   with the constraint:  \n   $$\n   \\text{taken}_{i,h} = 0 \\quad \\text{if} \\quad \\sum_{j=1}^{i-1} \\text{taken}_{j,h} \\geq C_h\n   $$\n\n4. **Capacity constraint at all times**:  \n   For all $ i \\in \\{1, \\dots, n\\} $ and all $ h \\in \\{0, \\dots, t\\} $:  \n   $$\n   p_{i,h} \\leq c_i\n   $$\n\n5. **No train after final hour**:  \n   After hour $ t-1 $, no train is dispatched, but the final state $ p_{i,t} $ must still satisfy $ p_{i,t} \\leq c_i $.\n\n---\n\n**Objective**  \nMinimize the total number of trains:  \n$$\n\\min \\sum_{h=0}^{t-1} x_h\n$$  \nsubject to the above constraints.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1007E","tags":["dp"],"sample_group":[["3 3 10\n2 4 10\n3 3 9\n4 2 8","2"],["4 10 5\n1 1 1\n1 0 1\n0 5 8\n2 7 100","12"]],"created_at":"2026-03-03 11:00:39"}}