Minimum Power Usage for Street Illumination

You are given a street of length \( l \) and \( n \) lamps. Each lamp is described by a tuple \((s_i, e_i, p_i)\), where \( s_i \) is the start position, \( e_i \) is the end position, and \( p_i \) is the power usage cost. The lamp covers every point on the street from \( s_i \) to \( e_i \) (inclusive). Your task is to choose a set of lamps such that the entire street from position 1 to \( l \) is continuously illuminated, and the total power usage is minimized.

If it is not possible to cover the entire street, output \( -1 \).

Note: The illumination intervals may overlap, and it is allowed to have redundant coverage. However, the objective is to minimize the sum of the costs of the selected lamps, while ensuring that every integer position from 1 to \( l \) is covered by at least one lamp.

The problem can be formulated as follows:

[ \text{Minimize } \sum_{\text{selected } i} p_i \quad \text{subject to} \quad \bigcup_{\text{selected } i} [s_i, e_i] \supseteq [1, l]. ]

inputFormat

The input is given via standard input (stdin) in the following format:

n l
s1 e1 p1
s2 e2 p2
... 
sn en pn

Where:

• n is the number of lamps.
• l is the length of the street.
• Each of the next n lines contains three integers: si, ei, and pi, representing the start position, end position, and power usage cost of the \(i\)-th lamp. It is guaranteed that \(1 \le s_i \le e_i \le l\).

outputFormat

The output should be printed to standard output (stdout) and consist of a single integer:

• The minimum total power usage required to illuminate the entire street from 1 to \( l \), or \( -1 \) if it is not possible.

## sample

4 10
1 5 2
4 10 3
2 7 4
8 10 5

5