2333번 - 생존과 탈출

어이쿠 발이 미끄러져 당신은 깊이 D의 함정에 빠졌다. 이 함정 안으로는 상자에 포장된 음식이 던져진다. 당신은 이 상자를 바닥에 쌓아서 탈출할 발판을 만들거나, 내용물을 먹어서 HP를 늘릴 수 있다. 상자 안이 비게 되면 발판을 만들어도 찌그러진다. 즉, 내용물을 먹는 것과 바닥에 쌓는 것을 동시에 할 수는 없다.

당신은 음식물을 먹으며 생존하면서 D이상의 높이로 상자를 쌓아서 탈출하려 한다. 함정 안으로 던져지는 상자들에 대한 정보가 주어졌을 때, 밖으로 탈출할 수 있게 되는 최소의 시간을 구하는 프로그램을 작성하시오. 현재 시각 = 0, HP = 10에서 시작한다. HP는 시간이 지날 때마다 1씩 감소한다. HP가 0이 되는 순간에 급히 음식을 먹으면 계속 생존할 수 있다.

두 자연수 D, G가 주어진다. D는 함정의 깊이, G는 던져지는 상자들의 개수이다. 다음 G개의 줄에는 상자에 대한 정보가 세 자연수 T, F, H로 주어진다. T는 이 상자가 던져지는 시각이다. F는 내용물을 먹었을 때 HP가 늘어나는 양이다. H는 이 상자를 쌓았을 때의 높이이다. 입력은 정렬되어 있지 않을 수 있다.

첫째 줄에 탈출할 수 있게 되는 최소의 시간을 출력한다. 만약 탈출할 수 없다면 생존할 수 있는 최대의 시간을 출력한다.

• 1 ≤ D ≤ 100
• 1 ≤ G ≤ 100
• 1 ≤ T ≤ 1000
• 1 ≤ F ≤ 30
• 1 ≤ H ≤ 25

첫 번째 상자를 쌓는다. 높이=9가 된다. 두 번째 상자는 내용물을 먹는다. 그러면 HP가 증가하여 13이라는 시각까지 생존해 있을 수 있게 된다. 세 번째 상자는 쌓는다. 높이가 10 증가하여 19가 된다. 네 번째 상자도 쌓으면 높이가 1 증가하여 20이 되고, 탈출할 수 있게 된다. 탈출해도 HP=0이라서 죽게 된다.