\(3^{rd}\) round, December \(7^{th}\), 2013

The mayor has decided that it is high time to implement a new system of television transmitters. The
city can be represented as a segment of the length D on which there are buildings of different
heights. The width of a building is negligible. On top of some buildings, television transmitters are
set, their dimensions are also negligible.

Television transmitters emit a television signal in all directions around them. The signal is spread
through space in straight lines and cannot pass through buildings. A certain point in the city is
considered covered if it is reached by a signal from an existing transmitter.

Find the segment of the city covered by television signal and output its length.

In test cases worth 30% of total points, N will be less or equal to 1000.

The first line of input contains the integer N (\(1 \le N \le 3 \cdot 10^{5}\)), the number of buildings, and the
integer D (\(1 \le D \le 10^{9}\)), the city length.
Each of the following N lines contains three numbers which describe the i^{th} building:
1. a number which determines whether there is a transmitter on top of the building: 0 (no) or 1
(yes)
2. an integer X_{i} (\(0 \le X_{i} \le D\)), the distance between the building and the left end of the city
3. an integer H_{i} (\(1 \le H_{i} \le 10^{9}\)), the building height
The buildings are sorted in ascending order by the distance from the left end of the city. No two
buildings will be located on the same distance from the left end of the city.

The first and only line of output must contain the required length from the text.
Note: the maximum permissible deviation from the official solution is \(10^{-3}\).
\(3^{rd}\) round, December \(7^{th}\), 2013

생성자가 기록되지 않았습니다.

출처 COCI 2013/2014 Contest 3