You must be very familiar with the game "Tetris". Now we consider a simplified version of this game. In this version, all the blocks are rectangle, and you even can't move the blocks horizontally when they are falling.
Given the description of the blocks series, which contains the horizontal position and the height of each block. You are requested to calculate the maximum height when all the blocks are landed by the given order.
The first line of each test case contains the number of the blocks N
and the width of the game arena W
. Then N
lines following. Each contains three integers Si
, which means the block's horizontal position is the interval [Si
] and the height of the block is Hi
You can assume W
≤ 1000, 1 ≤ Si
, 1 ≤ Hi
The input is terminated with W
Output one number for each test case, containing the maximum height.
1 3 2
3 4 5
6 7 6
The figure below describes the sample case.