Minimum Cost Continuous Barn Cleaning

John has a herd of very pampered cows that refuse to tolerate any dirt in their barn. In order to keep the barn clean during a specified time period, John must hire some of his cows to clean continuously. There are \( N \) cows (\(1 \leq N \leq 10000\)) willing to work for a fee, and the cleaning period is from second \( M \) to second \( E \) (\(0 \leq M \leq E \leq 86399\)). Note that the cleaning period lasts for \( E - M + 1 \) seconds.

Each cow provides their available work interval and required salary. Specifically, a cow is willing to work from second \( T_1 \) to second \( T_2 \) every day (with \( M \leq T_1 \leq T_2 \leq E \)) and asks for \( S \) dollars (\(0 \leq S \leq 500000\)). If a cow works from \( T_1 \) to \( T_2 \), then she cleans for \( T_2 - T_1 + 1 \) seconds.

When John hires a cow, he must pay her full salary even if her working period exceeds the current need. Moreover, the cows insist that during the entire cleaning period every second must be covered by at least one cleaning cow. Your task is to help John decide which cows to hire such that the entire interval from \( M \) to \( E \) is covered, and the total cost is minimized. If it is impossible to cover the interval continuously, output -1.

Note on continuity: Suppose a cow works from second 10 to 20, she covers 11 seconds (10, 11, ..., 20).

inputFormat

The input consists of multiple lines. The first line contains three integers: \( N\), \( M\), and \( E \). Each of the next \( N \) lines contains three integers: \( T_1\), \( T_2\), and \( S \) describing a cow's available time interval and her salary.

Example:

3 0 10
0 5 5
4 10 7
6 10 4

outputFormat

Output the minimum total cost to cover the entire period from \( M \) to \( E \). If it is impossible to cover the period continuously, output -1.

For the sample above, the correct output is:

9

sample

3 0 10
0 5 5
4 10 7
6 10 4

9