Description

John’s cows have been spoiled since childhood, and they cannot tolerate any dirt in the barn. John finds that, to satisfy these clean-freak cows, he has to hire some of them to clean the barn. Among John’s cows, there are $N(1 \leq N \leq 10000)$ cows who are willing to earn some pocket money by cleaning.

During a certain time period, the cows will litter in the barn at any time and anywhere. Naturally, they require that, throughout this period, at least one cow must be cleaning at all times. The required cleaning period starts at the $M$-th second of a day and ends at the $E$-th second $(0 \leq M \leq E \leq 86399)$. Note that “seconds” here refer to time intervals rather than time points. In other words, the total time that must be covered each day is $E - M + 1$ seconds.

John has obtained from each cow the work schedule she is willing to accept: for a given cow, she is willing to work every day during the interval from the $T_1$-th second to the $T_2$-th second $(M \leq T_1 \leq T_2 \leq E)$, and she asks for a payment of $S$ dollars $(0 \leq S \leq 500000)$. As with the required cleaning period, if a cow is willing to work from the 10-th to the 20-th second each day, then her total working time is 11 seconds, not 10 seconds.

Once John decides to hire a cow, he must pay her the full wage. He cannot hire her for only part of her available time and then pay a fraction based on how much of her available time she actually worked. Please help John decide which cows to hire to keep the barn clean. Of course, while keeping the cows satisfied, John wants the total cost to be as small as possible.

Input Format

Line 1: Three positive integers $N, M, E$.

Lines 2 to $N + 1$: Line $i + 1$ gives the work schedule of cow $i$, i.e. three positive integers $T_1, T_2, S$.

Output Format

Output one integer, the minimum total cost John needs to pay for cleaning the barn. If it is impossible to complete the cleaning, output $-1$.

3 0 4
0 2 3
3 4 2
0 0 1

5

Hint

John has 3 cows, and the barn needs to be cleaned from the 0-th second to the 4-th second. John can hire the first two cows and complete a whole day of cleaning with only 5 dollars.

Translated by ChatGPT 5