테트루지 박스

시간 제한5초메모리 제한1024 MB

요약

너비가 b인 바닥에 직사각형 블록을 차례로 떨어뜨려, 쌓인 뒤 가장 높은 열의 높이를 구합니다.

난이도: 쉬움10점 중 3점
유형: 배열, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

Orooji 박사의 자녀들은 테트리스를 해 봤지만, 관련 문제를 O 박사와 함께 풀고 싶어 하지 않는다. O 박사의 자녀들은 O 박사가 오늘날 100명이 넘는 뛰어난 문제 해결사와 프로그래머에게 접근할 수 있는 행운을 누리고 있다는 사실을 깨닫지 못한다!

O 박사는 2차원 상자의 바닥 길이를 알고 있고, 상자에 필요한 높이를 구하려 한다. O 박사는 바닥 위에 2차원 블록(직사각형)을 여러 개 떨어뜨린다. 블록은 바닥에 닿거나 이미 떨어진 블록에 막힐 때까지 아래로 내려간다(즉, 그 블록 위에 놓인다). 모든 블록을 떨어뜨린 뒤, 가장 높은 열의 높이가 상자에 필요한 높이가 된다. 그림은 힌트 부분을 참고한다.

입력

첫 줄에는 두 정수 $b$ ( $1 \le b \le 100$ )와 $r$ ( $1 \le r \le 50$ )이 주어진다. $b$ 는 바닥의 길이이고, $r$ 은 블록의 개수이다. 이어지는 $r$ 개의 줄에는 세 정수가 주어진다. 블록의 가로 길이 $h$ ( $1 \le h \le 100$ ), 세로 길이 $v$ ( $1 \le v \le 100$ ), 그리고 블록이 떨어지는 가장 왼쪽 열 $c$ ( $c \ge 1$ )이다. $h$ 와 $c$ 는 블록이 바닥을 벗어나지 않도록 주어진다. 즉 $(c + h - 1) \le b$ 이다.

출력

상자에 필요한 높이를 출력한다. 가장 높은 열의 높이가 필요한 높이이다.

힌트

예제2

예제 1
입력
```
10 4
2 3 1
4 2 2
1 7 6
1 3 4
```
예상 출력
```
8
```
예제 2
입력
```
10 3
3 4 8
8 2 1
1 1 3
```
예상 출력
```
7
```