Minimum Sequence Length Under Interval Constraints

You are given an unknown-length sequence of distinct integers. You do not know the length of the sequence in advance. However, you are provided with several constraints in the form of intervals. Each constraint is given by a triple \((L_i, R_i, C_i)\), which means that the sequence must contain at least \(C_i\) numbers in the interval \([L_i, R_i]\) (i.e. numbers \(x\) such that \(L_i \le x \le R_i\)). Determine the minimum possible length of the sequence such that all the given constraints are satisfied.

Note: The integers in the sequence are all distinct.

Input Format (also see below):

• The first line contains a single integer n, representing the number of constraints.
• Each of the following n lines contains three space-separated integers \(L_i\), \(R_i\), and \(C_i\), representing a constraint.

Output Format (also see below):

• Output a single integer, the minimum possible length of the sequence.

Algorithm Hint: A greedy approach can be used. Sort the intervals by their right endpoint \(R_i\) in ascending order. For each interval, count how many numbers have already been chosen that fall within the current interval \([L_i, R_i]\). If this count is less than \(C_i\), add the necessary number of integers starting from \(R_i\) and decrementing, ensuring that each chosen number is distinct. This way, the integers you choose may satisfy future intervals as well.

Mathematical Expression:

For each interval \( (L_i, R_i, C_i) \), ensure that \[ |\{ x \in S : L_i \le x \le R_i \}| \ge C_i, \] where \(S\) is the set of chosen integers. The task is to minimize \(|S|\).

inputFormat

The input begins with a single integer n on the first line, representing the number of constraints.

Then, n lines follow. Each line contains three space-separated integers \(L_i\), \(R_i\), and \(C_i\), which indicate that there must be at least \(C_i\) integers from the sequence in the interval \([L_i, R_i]\).

outputFormat

Output a single integer representing the minimum possible length of the sequence of distinct integers that satisfies all the given constraints.

sample

3
1 3 2
2 4 1
2 2 1

2