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 adjacency_list
import sys

INF=sys.maxsize

def BFS(G,start,vertex_list):
    for nodes in vertex_list:
        G.SetVertexValue(nodes,[None,INF])
    G.SetVertexValue(start, [None,0])
    Q=[]
    Q.append(start)
    while Q.__len__() is not 0:
        v=Q[0]
        Q.remove(v)
        for node in vertex_list:
            if G.IsAdjacent(v,node) and G.GetVertexValue(node)[1]==INF:
                G.SetVertexValue(node, [v, G.GetVertexValue(v)[1]+1])
                Q.append(node)
    return G

def Augment(G,f,P,vertex_list):
    # P is a path in residual graph
    # b is the minimal weight in path P
    b=INF
    edge_set=[]
    for node1 in vertex_list:
        for node2 in vertex_list:
            if P.IsAdjacent(node1,node2):
                edge_set.append([node1,node2])
                weight=P.GetEdgeWeight(node1,node2)
                if weight<b:
                    b=weight
    for edge in edge_set:
        if G.IsAdjacent(edge[0],edge[1]):
            # in this case, it is a forwarding path
            if f.IsAdjacent(edge[0],edge[1]):
                # if this edge exits, enlarge it
                new_weight=f.GetEdgeWeight(edge[0], edge[1])+b
                f.SetEdgeWeight(edge[0], edge[1], new_weight)
            else:
                f.AddEdge(edge[0], edge[1], b)
        else:
            # in this case, it is a backward path
            new_weight = f.GetEdgeWeight(edge[0], edge[1]) - b
            f.SetEdgeWeight(edge[0], edge[1], new_weight)
    return f

def Ford_Fulkerson(G,start,terminate,vertex_list):
    f = adjacency_list.Graph()
    for node in vertex_list:
        f.AddVertex(node)
    edge_set=[]
    for node1 in vertex_list:
        for node2 in vertex_list:
            if G.IsAdjacent(node1,node2):
                edge_set.append([node1,node2])
                f.AddEdge(node1,node2,0)

    flag=True

    while flag:
        # create a residual graph
        GF = adjacency_list.Graph()
        for node in vertex_list:
            GF.AddVertex(node)
        for edge in edge_set:
            w=G.GetEdgeWeight(edge[0],edge[1])-f.GetEdgeWeight(edge[0],edge[1])
            if w!=0:
                GF.AddEdge(edge[0],edge[1],w)
            if f.GetEdgeWeight(edge[0],edge[1])!=0:
                GF.AddEdge(edge[1], edge[0], f.GetEdgeWeight(edge[0],edge[1]))
        Path=BFS(GF, start, vertex_list)
        # output the path contained in GF
        P = adjacency_list.Graph()
        V=[]
        V.append(terminate)
        point=terminate
        if Path.GetVertexValue(terminate)[0] is None:
            flag=False
            break
        else:
            while point!=start:
                point=Path.GetVertexValue(point)[0]
                V.append(point)
        V.reverse()
        for vertex in V:
            P.AddVertex(vertex)
        for i in range(0,V.__len__()-1,1):
            P.AddEdge(V[i],V[i+1],GF.GetEdgeWeight(V[i],V[i+1]))
        f=Augment(G, f, P, vertex_list)
    return f


G = adjacency_list.Graph()
G.AddVertex('s')
G.AddVertex('d')
G.AddVertex('b')
G.AddVertex('e')
G.AddVertex('c')
G.AddVertex('t')
G.AddEdge('s', 'd', 10)
G.AddEdge('d', 'e', 4)
G.AddEdge('e', 't', 10)
G.AddEdge('s', 'b', 10)
G.AddEdge('b', 'c', 9)
G.AddEdge('c', 't', 10)
G.AddEdge('d', 'b', 2)
G.AddEdge('c', 'e', 6)
G.AddEdge('d', 'c', 8)
v_list=['s','d','b','e','c','t']

# G.AddVertex('s')
# G.AddVertex('v1')
# G.AddVertex('v2')
# G.AddVertex('v3')
# G.AddVertex('v4')
# G.AddVertex('t')
# G.AddEdge('s', 'v1', 16)
# G.AddEdge('s', 'v3', 13)
# G.AddEdge('v1', 'v2', 12)
# G.AddEdge('v2', 'v3', 9)
# G.AddEdge('v1', 'v3', 10)
# G.AddEdge('v3', 'v1', 4)
# G.AddEdge('v3', 'v4', 14)
# G.AddEdge('v4', 'v2', 7)
# G.AddEdge('v2', 't', 20)
# G.AddEdge('v4', 't', 4)
# v_list=['s','v1','v2','v3','v4','t']

start='s'
terminate='t'
f= adjacency_list.Graph()
f=Ford_Fulkerson(G,start,terminate,v_list)
flow=0
for nodes in v_list:
    if f.IsAdjacent(start,nodes):
        flow+=f.GetEdgeWeight(start,nodes)
f.Print()
print("flow=",flow)



