Escape from the Garbage Well

Carmen, a precious Holsteins cow, has fallen into the "Garbage Well", a pit with a depth of \(D\) feet where farmers discard their garbage. To escape, Carmen must use the garbage pieces to build a pile such that its total height is at least \(D\). Each garbage piece arrives at a known time \(t\) (\(1\le t\le 1000\)). When a piece arrives, Carmen can choose to either stack it, which increases the pile height by \(h\) (\(1\le h\le 25\)), or eat it to extend her survival time by \(f\) hours (\(1\le f\le 30\)). Initially, Carmen has enough energy to survive for 10 hours. If she goes 10 hours without eating (i.e. if the time gap from her last meal reaches 10 hours), she will starve. (Note that if her remaining time exactly reaches 0, she can still eat or escape without starving.)

Determine the earliest time at which Carmen can escape the well. If it is impossible for her to escape, output -1.

Approach Overview:

• Sort the garbage pieces by their arrival time \(t\).
• Use dynamic programming where dp[i] represents the maximum expiration time (in hours) that can be achieved with a piled height of i feet.
• For each garbage piece at time \(t\) with attributes \(h\) and \(f\), if it arrives before the current expiration time, update the state by either eating (which increases the expiration time by \(f\)) or stacking the piece (which increases the pile height by \(h\)).
• If stacking causes the pile height to reach or exceed \(D\), record the current event time as a candidate for the escape time.
• Output the minimum such escape time, or -1 if escape is impossible.

inputFormat

The first line contains two integers: \(D\) (the well depth in feet) and \(n\) (the number of garbage pieces).

Each of the next \(n\) lines contains three integers \(t\), \(h\), and \(f\), representing:

• \(t\): The time (in hours) when the garbage piece is dropped.
• \(h\): The height added to the pile if the garbage is stacked.
• \(f\): The extra survival time (in hours) gained if the garbage is eaten.

outputFormat

Output a single integer: the earliest time at which Carmen can escape the well by having the pile height \(\ge D\). If it is impossible for her to escape, output -1.

sample

10 3
1 3 5
3 8 2
10 2 1

3