생존과 탈출

발을 헛디뎌 깊이 D인 함정에 빠졌다. 함정 안으로는 음식이 들어 있는 상자가 차례로 떨어진다. 상자 하나를 받으면 두 가지 중 하나만 선택할 수 있다. 내용물을 먹어 HP를 늘리거나, 먹지 않은 상자를 바닥에 쌓아 발판의 높이를 높이는 것이다. 상자를 비운 뒤에는 발판으로 쓸 수 없으므로, 같은 상자를 먹는 데 쓰고 쌓는 데에도 쓸 수는 없다.

시각 0에 HP 10으로 시작한다. 시간이 1 흐를 때마다 HP는 1 감소한다. HP가 0이 되는 바로 그 순간에 도착한 음식을 먹을 수 있다면 계속 생존할 수 있다. 주어진 상자들을 이용해 쌓은 높이가 D 이상이 되어 탈출할 수 있는 가장 이른 시각을 구하라.

첫째 줄에 두 자연수 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를 만들고, 두 번째 상자는 먹어 생존 가능 시각을 13까지 늘리는 것이다. 세 번째 상자를 쌓으면 높이가 19가 되고, 네 번째 상자까지 쌓으면 높이가 20이 되어 탈출한다. 탈출 순간 HP가 0이라서 죽는다는 뜻은 아니다.