Depot













We have acquired a state-of-the-art ore processing facility, supposedly "to
evaluate whether gzip can produce diamonds". The facility sequentially processes
ore through  stages, from a crude stage , to the final stage .

Each stage of refinement can consist of several machines. Each machine converts
material  into material , but their efficiency varies, and only one is
available at a time. Machine specifications detail how many units of an input
material they consume and how many units of an output material they produce.

Storage being expensive, all input and output materials are stored in the same
shared warehouse with maximum capacity . Excess material can be sent away
from the warehouse for disposal at any time.

Each stage must occur in-order; once any stage of processing is completed, it
cannot be revisited.

As the new operations manager your task is to determine the maximum quantity of
material  that can be produced, given your initial stockpile of raw material
 and limited warehouse capacity .

Input
    
        One line containing the number of materials  (), and the number of machines  ().
        One line containing the initial quantity of material 1, , and the capacity of the warehouse  ()
         lines, each describing a machine, consisting of three integers:
        
             (), the input material (The machine converts material  into material ).
             (), the amount of material  consumed.
             (), the amount of material  produced.
            
Output
    Output an integer, the maximum final quantity of material .