페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7025
서브태스크

생존과 탈출 1초 128MB

문제

정올이는 깊이 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


출력

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


부분문제

번호 점수 조건
#110점

G=1

#220점

T=1

#330점

D \le 10, G\le10, T\le20

#440점

추가 제한 없음


예제1

입력
204
549
932
12610
1311
출력
13

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



태그

출처

USACO 2001 US Open Green

역링크