시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 16 1 1 50.000%

문제

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

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

입력

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

출력

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

예제 입력

20 4
5 4 9
9 3 2
12 6 10
13 1 1

예제 출력

13

힌트

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