Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

2885.   Tetris
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 1273   Accepted Runs: 397

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, Ei, Hi, which means the block's horizontal position is the interval [Si, Ei] and the height of the block is Hi.

You can assume W ≤ 109, N ≤ 1000, 1 ≤ SiEiW, 1 ≤ Hi ≤ 1000.

The input is terminated with W = N = 0.


Output one number for each test case, containing the maximum height.

Sample Input

3 10
1 3 2
3 4 5
6 7 6
0 0

Sample Output

Hint: The figure below describes the sample case.

Source: TJU Team Selection Contest 2007 (5)
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:G.D.Retop. Developer: SuperHacker, G.D.Retop