Flight Gate Scheduling

There are a+b parking positions at an airport. Among these, a positions are connected to the terminal via jet bridges, and the remaining b are not. If a plane is parked at a position without a jet bridge, its passengers must use a shuttle bus, which causes each passenger a unit of discomfort.

When a plane is scheduled for boarding at time \(s\), it must choose an available parking position. At time \(s\), all passengers board the plane. The plane stays at that position until its departure time \(t\). Note that if a plane departs at time \(x\), then at time \(x\) its parking position becomes free.

To reduce the total discomfort, the management allows a plane to switch its parking position during the interval \([s, t]\). Specifically, if a plane starts switching from position A to position B at time \(x\), then position A becomes free at time \(x+1\). Such a switch is only allowed if position B is free at time \(x+1\>.

A flight’s discomfort is equal to its number of passengers if it boards at a position without a jet bridge, and 0 if it boards at a jet‐bridge position. Thanks to the switching rule, if there is at least one non–jet-bridge position (i.e. \(b>0\)), then at any boarding time the airport can ensure that a jet-bridge positions are available by letting flights that boarded earlier switch to non–jet-bridge positions immediately after boarding. However, when \(b=0\) there is no possibility of switching, and a position, once used, remains occupied until the plane departs (note that if two flights board at the same time, they cannot share the same position).

Given the number of passengers, boarding time, and departure time for each flight, compute the minimum total discomfort possible.

inputFormat

The first line contains two integers: a and b, representing the number of jet-bridge positions and non–jet-bridge positions, respectively.

The second line contains an integer n, the number of flights.

Each of the following n lines contains three integers: p, s, and t, where p is the number of passengers, s is the boarding time, and t is the departure time.

outputFormat

Output a single integer: the minimum total discomfort (i.e. the sum of the number of passengers who end up boarding via the shuttle bus).

sample

1 1
3
100 1 5
50 1 4
200 2 6

50