Tetrooj Box

Dr. Orooji's children have played Tetris but are not willing to help Dr. O with a related problem. Dr. O's children don't realize that Dr. O is lucky to have access to 100+ great problem solvers and great programmers today!

Dr. O knows the length of the base for a 2D box and wants to figure out the needed height for the box. Dr. O will drop some 2D blocks (rectangles) on the base. A block will go down until it lands on the base or is stopped by an already-dropped block (i.e., it lands on that block). After all the blocks have been dropped, the needed height for the box is determined by the tallest column. See the pictures in the hint section.

The first input line contains two integers: $b$ ($1 \le b \le 100$), the length of the base, and $r$ ($1 \le r \le 50$), the number of blocks. Each of the next $r$ lines contains three integers: a block's horizontal length $h$ ($1 \le h \le 100$), its vertical length $v$ ($1 \le v \le 100$), and $c$ ($c \ge 1$), the leftmost column the block is dropped into. The values of $h$ and $c$ are such that the block does not go beyond the base, i.e., $(c + h - 1) \le b$.

Print the needed height for the box. The tallest column is the height.