Microbiology Lab

A research lab wants to observe N types of microbes by growing them at several temperatures.

Microbe i can be grown only at an integer temperature from A[i] through B[i], inclusive. For the experiment to be sufficient, microbe i must be grown in at least C[i] laboratories whose temperatures are all different.

Each laboratory is kept at one fixed integer temperature, and no two laboratories have the same temperature. If a laboratory has temperature T, then any number of microbes of any types satisfying A[i] ≤ T ≤ B[i] may be grown there.

All temperatures are integers from 0 to 50,000, inclusive. Find the minimum number of laboratories needed to satisfy every condition.

The first line contains N, the number of microbe types. Each of the next N lines contains A[i], B[i], and C[i] for i = 1, 2, ..., N, in that order.

Print the minimum number of laboratories needed.

• 1 ≤ N ≤ 50,000
• 0 ≤ A[i] ≤ B[i] ≤ 50,000
• 1 ≤ C[i] ≤ B[i] - A[i] + 1

Laboratories at temperatures 1 and 3 are sufficient.