17.10.5 Prob III - Security
题目描述
断罪小学附近有一条“十里飘香”的小吃街，然而近来频繁的打架斗殴事件让这里的声誉急剧下跌。为了稳住消费者，小吃街的总经理决定斥资雇佣一批保安。
小吃街上共有\(K\)家店铺，间隔均匀地排成一排。有\(N\)名保安愿意被雇佣，第\(i\)名保安负责监控第\(s_i \sim e_i\)家店铺，收取的佣金为\(c_i\)。
现要求每家店铺都至少有1名保安监控着，请你编写程序帮总经理出谋划策，计算他最少应该出多少佣金？
输入格式
第一行是两个正整数\(N,K\)；
之后\(N\)行，第\(i\)行包含3个非负整数\(s_i, e_i, c_i\)。
20%的数据：\(N \le 10\)；
另20%的数据：\(c_i = 1\)；
另20%的数据：\(N \le 500, \quad K \le 2000\)；
100%的数据：\(N \le 10^4, \quad K \le 10^5, \quad 1 \le s_i \le e_i \le K, \quad 0 \le c_i \le 5 \times 10^5\)。
输出格式
一个整数：如果不可能使每家店铺都被监控，输出-1；否则，输出最少需要的佣金。
数据保证答案\(\le 10^9\)。
样例
input
3 5
1 3 3
4 5 2
1 1 1
output
5
限制
Time limit: 1 sec
Memory limit: 128 megabytes
来源
From Vijos Official Domain (p1404)
https://vijos.org/p/1404
