You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn. 
Write a program that: 
reads the number of intervals, their end points and integers c1, ..., cn from the standard input, 
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n, 
writes the answer to the standard output. 

The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.

5

3 7 3

8 10 3

6 8 1

1 3 1

10 11 1

6

 //It is made by jump~

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <ctime>

 #include <vector>

 #include <queue>

 #include <map>

 #ifdef WIN32

 #define OT "%I64d"

 #else

 #define OT "%lld"

 #endif

 using namespace std;

 typedef long long LL;

 const int inf = (<<);

 const int MAXN = ;

 const int MAXM = ;

 int n;

 int first[MAXN],next[MAXM],to[MAXM],w[MAXM];

 int dis[MAXN];

 bool pd[MAXN];

 int ecnt;

 int Min,Max;

 int ans;

 queue<int>Q;

 inline int getint()

 {

        int w=,q=;

        char c=getchar();

        while((c<'' || c>'') && c!='-') c=getchar();

        if (c=='-')  q=, c=getchar();

        while (c>='' && c<='') w=w*+c-'', c=getchar();

        return q ? -w : w;

 }

 inline void Init(){

     ecnt=; memset(first,,sizeof(first));

     Max=; Min=inf;

     while(!Q.empty()) Q.pop();

     ans=;

 }

 inline void link(int x,int y,int z){

     next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; w[ecnt]=z;

 }

 inline void spfa(){

     for(int i=;i<=n;i++) dis[i]=-inf;

     Q.push(Min); pd[Min]=; dis[Min]=;

     while(!Q.empty()) {

     int u=Q.front(); Q.pop(); pd[u]=;

     for(int i=first[u];i;i=next[i]) { //最长路

         int v=to[i];

         if(dis[v]<dis[u]+w[i]) {

         dis[v]=dis[u]+w[i];

         if(!pd[v]){

             Q.push(v); pd[v]=;

         }

         }

     }

     }

     ans=dis[Max];

 }

 inline void solve(){

     while(scanf("%d",&n)!=EOF){

         Init();

     int x,y,z;

     for(int i=;i<=n;i++) {

         x=getint()-;y=getint();z=getint();

         link(x,y,z);

         Min=min(Min,x); Max=max(Max,y);

     }

     for(int i=Min;i<Max;i++){//以前缀和为结点

         link(i+,i,-); link(i,i+,);//要使所有点满足s[i+1]-s[i] <= 1 &&  s[i]-s[i+1] <= 0

     }

     spfa();

     printf("%d",ans);

     }

 }

 int main()

 {

   solve();

   return ;

 }