[USACO05DEC] Cleaning Shifts S

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

需要在每天第 $M$ 秒到第 $E$ 秒（两端均包含）的每一秒安排至少一头奶牛打扫。共有 $N$ 头奶牛愿意工作；第 $i$ 头奶牛可覆盖连续时段 $[T_1,T_2]$，雇佣她需要支付固定工资 $S$。一旦雇佣就必须支付全额工资。

求覆盖整个 $[M,E]$ 时段的最小总工资；若无法完整覆盖，输出 $-1$。

输入格式

第一行三个整数 $N,M,E$。接下来 $N$ 行每行三个整数 $T_1,T_2,S$。

输出格式

输出最小总工资，无法覆盖则输出 $-1$。

样例输入 1

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

样例输出 1

5

数据范围

• $1\le N\le10000$；
• $0\le M\le E\le86399$；
• $M\le T_1\le T_2\le E$；
• $0\le S\le500000$。