Intervals 区间

题目描述:

给定n个闭区间[a_i，b_i] （1<=i<=n<=1000 ， 0<=ai<=bi<=50,000 ) 和 n个整数ci ( 1<=i<=n )，你需要构造一个集合Z，使得对于任何的i∈[1，n]，Z中满足x∈[a_i，b_i]的x不少于c_i个，求这样的整数集合Z至少包含多少个数。

简而言之就是从0~50,000中选出尽量少的整数， 使每个区间[a_i，b_i] 内都有至少ci个数被选出。

输入格式:

第一行包括一个整数n，表示区间个数，以下n行每行描述这些区间，第i+1行三个整数ai, bi，ci，由空格隔开，其中1<=ai <= bi <= 50,000 而且 1<= ci <= bi-ai+1。

输出格式:

一行，输出满足要求的序列最少整数的个数。

样例输入:

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

样例输出:

6

时间限制: 1000ms
空间限制: 256MB

---