Rail Car Allocation

There is a circular railway which has \(n\) stations labeled from 1 to \(n\) arranged in clockwise order. A train runs along this circular route. During the New Year travel rush, there are \(m\) ticket requests in the early hours of New Year’s Eve. Each request is given as a triple \((x, y, z)\), meaning that \(z\) people want to travel clockwise from station \(x\) to station \(y\). When the train stops at any station \(x\), all people waiting to board at station \(x\) will board the train and all people whose destination is \(x\) will get off, simultaneously.

The starting station is not fixed. We can choose an optimal starting station so that the peak number of passengers at any time during the journey is minimized. Each rail car has a capacity of \(36\) people. Your task is to calculate the minimum number of rail cars needed so that the train can carry all its passengers throughout its entire journey.

Note: For each ticket request \((x, y, z)\), interpret the request as follows: add \(z\) passengers at station \(x\) and subtract \(z\) passengers at station \(y\). Even if \(x > y\) (i.e. the request wraps around the circle), the same update applies. Let the differential contribution at station \(i\) be \(d_i\). If you calculate the prefix sum (cumulative number of boarded passengers) over the stations for a chosen starting station, the maximum occupancy during that journey can be minimized by an appropriate shift. In fact, if \(P_i\) is the cumulative sum sequence (with \(P_0=0\)), then by choosing the starting station optimally the minimum possible maximum occupancy is \(\max(P_i) - \min(P_i)\). The answer is therefore \(\lceil (\max(P_i)-\min(P_i))/36 \rceil\).

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of stations and the number of ticket requests, respectively.

Each of the following \(m\) lines contains three integers \(x\), \(y\) and \(z\) indicating a ticket request: \(z\) people want to travel from station \(x\) to station \(y\) in clockwise order.

outputFormat

Output a single integer: the minimum number of rail cars required to complete the transportation. (Each car can hold exactly 36 people.)

sample

4 1
1 3 10

1