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.

A 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.

If multiple trains are appointed to the same hour, their capacities are being added up and they are moving together.

The player wants to stay in the game for $t$ hours. Determine the minimum number of trains he will need for it.
The 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.

Each 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.
import copy

class challenge:
    def __init__ (self):
        self.itinerary = 0          # the itinerary is a constant 
        self.truck_capacity = 0     # the capacity of the truck
        self.warehouse = []         # the list of warehouse
        self.package_add = {}       # the number of packages added to the warehouse every hour
        self.package = {}           # the number of packages
        self.capacity = {}          # the capacity of warehouse
        self.memorize = {}          # memorize
        self.stack = []

    def AddWarehouse(self,warehouse,package,package_add,capacity):
        self.warehouse.append(warehouse)
        self.package[warehouse] = package
        self.package_add[warehouse] = package_add
        self.capacity[warehouse] = capacity

    def SetTime(self,itinerary):
        self.itinerary = itinerary

    def SetCapacity(self,capacity):
        self.truck_capacity = capacity

    def isValid(self):
        for warehouse in self.warehouse:
            if self.package[warehouse] > self.capacity[warehouse]:
                return False
        return True

    def isEmpty(self):
        for warehouse in self.warehouse:
            if self.package[warehouse] > 0:
                return False
        return True   

    def SendTruck(self):
        capacity = self.truck_capacity
        for warehouse in self.warehouse:
            if capacity <= self.package[warehouse]:
                self.package[warehouse] = self.package[warehouse] - capacity
                break
            capacity = capacity - self.package[warehouse]
            self.package[warehouse] = 0

    def AddPackage(self):
        for warehouse in self.warehouse:
            self.package[warehouse] = self.package[warehouse] + self.package_add[warehouse]

    def SubPackage(self):
        for warehouse in self.warehouse:
            self.package[warehouse] = self.package[warehouse] - self.package_add[warehouse]

    # return the minimum trucks needed to survive 'time'
    def Search(self, time):
        package = copy.deepcopy(self.package)
        # finish searching
        if time == self.itinerary:
            truck = 0
            self.AddPackage()
            while self.isValid() is not True:
                self.SendTruck()
                truck = truck + 1
            self.package = copy.deepcopy(package)
            return truck
        # search in memorized hash table
        key = '.'.join([str(self.package[x]) for x in self.package]) + '.' + str(time)
        if key in self.memorize:
            return self.memorize[key]
        # search 'time + 1'
        truck = 0
        choice = []
        while True:
            # prun if the package distribution violate the limit
            if time > 0:
                self.AddPackage()
            if self.isValid():
                ans = self.Search(time+1)
                choice.append(ans + truck)
            if time > 0:      
                self.SubPackage()
            # prun if the all warehouse is empty
            if self.isEmpty():
                break
            # recursively send truck
            self.SendTruck()
            truck = truck + 1
        self.package = copy.deepcopy(package)
        # choose the best result
        self.memorize[key] = min(choice)
        return min(choice)

    
    def Solve(self):
        # initialize the prefix sum
        ans = self.Search(0)
        print(ans)

problem = challenge()
content1=input().split()
cityCount = int(content1[0])
capacityCount = int(content1[2])
timeCount = int(content1[1])

problem.SetTime(timeCount)
problem.SetCapacity(capacityCount)

# initial = [int(x) for x in input().split()]
# increase = [int(x) for x in input().split()]
# capacity = [int(x) for x in input().split()]
initial=[]
increase=[]
capacity=[]
for i in range(cityCount):
    content=input().split()
    initial.append(int(content[0]))
    increase.append(int(content[1]))
    capacity.append(int(content[2]))

for city in range(cityCount):
    problem.AddWarehouse(str(city),initial[city],increase[city],capacity[city])
problem.Solve()
