/*

 problem:yibentong10000

 date:2019/4/21

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn = 1e3+;

 struct node{

     int s,f,dif;

 };

 node a[maxn];

 int n,ans;

 inline void init(){

     cin>>n;

     for(int i =;i <= n;i++)scanf("%d%d",&a[i].s,&a[i].f);

 }

 inline bool cmp(node x,node y){

     return x.f < y.f;

 }

 int main(){

     init();

     sort(a+,a++n,cmp);

     ans = ;

     int tmp = a[].f;

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

         if(a[i].s >= tmp){

             ans++;

             tmp = a[i].f;

         }

     cout<<ans<<endl;

     return ;

 }

 /*

 problem:yibentong10001

 date:2019.4.21

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn = 3e4+;

 struct node{

     int b,e,t;

 }a[maxn];

 int visit[maxn];

 int n,ans,h;

 inline void init(){

     cin>>n;

     cin>>h;

     for(int i = ;i <= h;i++)

         scanf("%d%d%d",&a[i].b,&a[i].e,&a[i].t);

 }

 inline bool cmp(node x,node y){

     return x.e < y.e;

 }

 int main(){

     init();

     sort(a+,a++h,cmp);

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

         int cnt = ;

         for(int j = a[i].b;j <= a[i].e;j++)

             cnt += visit[j];

         if(cnt >= a[i].t)continue;

         for(int j = a[i].e;j >= a[i].b;j--)

             if(!visit[j]){

                 visit[j] = ;

                 cnt++;

                 ans++;

                 if(cnt == a[i].t)break;

             }

     }

     cout<<ans<<endl;

     return ;

 }

 /*

 problem:yibentong10002

 date:2019/4/21

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int maxn = 25e3+;

 struct node{

     double head,tail;

 }a[maxn];

 int n,l,w,T,cnt,ans;

 inline bool cmp(node x,node y){

     return x.head < y.head;

 }

 inline void init(){

     cin>>n>>l>>w;

     cnt = ;

     for(int i = ,r,position;i <= n;i++){

         scanf("%d%d",&position,&r);

         if(r <= w/)continue;

         cnt++;

         double tmp = r*r-w*w/4.0;

         a[cnt].head = position-sqrt(tmp);

         a[cnt].tail = position+sqrt(tmp);

     }

 }

 int main(){

     cin>>T;

     while(T--){

         init();

         sort(a+,a++cnt,cmp);

         ans = ;

         double position = ;

         bool flag = false;

         while(position < l){

             ans++;

             double tmp = position;

             for(int i = ;a[i].head <= tmp && i <= cnt;i++)

                 if(position < a[i].tail)

                     position = a[i].tail;

             if(position == tmp && position < l){

                 puts("-1");

                 flag = true;

                 break;

             }

         }

         if(flag == false)cout<<ans<<endl;

     }

     return ;

 }

 /*

 problem:yibentong10003

 date:2019/4/30

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int maxn = 1e3+;

 struct node{

     int position,Min;

 }p[maxn];

 int a[maxn],b[maxn],ans[maxn];

 int n;

 inline void init(){

     cin>>n;

     for(int i = ;i <= n;i++)scanf("%d",&a[i]);

     for(int i = ;i <= n;i++)scanf("%d",&b[i]);

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

         p[i].Min = min(a[i],b[i]);

         p[i].position = i;

     }

 }

 inline bool cmp(node x,node y){

     return x.Min < y.Min;

 }

 int main(){

     init();

     sort(p+,p++n,cmp);

     int tmph = ,tmpt = n+;

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

         if(p[i].Min == a[p[i].position]){tmph++;ans[tmph] = p[i].position;}

         else{tmpt--;ans[tmpt] = p[i].position;}

     int timea = ,timeb = ;

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

         timea += a[ans[i]];

         if(timeb < timea)timeb = timea;

         timeb += b[ans[i]];

     }

     cout<<timeb<<endl;

     for(int i = ;i <= n;i++)printf("%d%c",ans[i],i == n ? '\n':' ');

     return ;

 }

 /*

 problem:yibentong10004

 date:2019/4/30

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn = 5e2+;

 struct node{

     int x,y;

 }a[maxn];

 int vis[];

 int flag,s;

 int cmp(node a,node b){

     return a.y > b.y;

 }

 int main(){

     int m,n;

     cin>>m>>n;

     for(int i = ;i <= n;i++)scanf("%d",&a[i].x);

     for(int i = ;i <= n;i++)scanf("%d",&a[i].y);

     sort(a+,a+n+,cmp);

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

         flag = ;

         for(int j = a[i].x;j >= ;j--)

             if(vis[j] == ){

                 flag = ;

                 vis[j] = ;

                 break;

             }

         if(flag == ){

             for(int k = n;k >= ;k--)

                 if(vis[k] == ){

                     vis[k] = ;

                     break;

                 }

             s += a[i].y;

         }

     }

     printf("%d\n",m-s);

     return ;

 }

 /*

 problem:yibentonglian10000

 date:2019/5/5

 author:Lonely.Devil

 */

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 using namespace std;

 const int maxn = 1e3+;

 int a[maxn];

 int n,Max,Min;

 int main(){

     cin>>n;

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

         scanf("%d",&a[i]);

     int tmp;

     cin>>tmp;

     sort(a+,a++n);

     Min = a[n];

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

         Min = Min*a[n-i]+;

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

         a[i+] = a[i]*a[i+]+;

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

             if(a[j] > a[j+])

                 swap(a[j],a[j+]);

     }

     Max = a[n];

     cout<<Max-Min<<endl;

     return ;

 }

 /*

 problem:yibentonglian10001

 date:2019/5/5

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 using namespace std;

 int n,m,ans,now;

 int main(){

     cin>>n>>m;

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

         scanf("%d",&tmp);

         now += tmp;

         if(now < m && i == n){

             ans++;

             break;

         }

         if(now > m){

             ans++;

             now = tmp;

         }

         if(now == m){

             ans++;

             now = ;

         }

     }

     cout<<ans<<endl;

     return ;

 }

 /*

 problem:yibentonglian10002

 date:2019/5/5

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int maxn = 1e6+;

 struct node{

     int x,y;

 }a[maxn];

 int n,now,ans;

 inline bool cmp(node a,node b){

     return a.y < b.y;

 }

 int main(){

     cin>>n;

     for(int i = ;i <= n;i++)scanf("%d%d",&a[i].x,&a[i].y);

     sort(a+,a++n,cmp);

     now = a[].y;

     ans = ;

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

         if(a[i].x >= now){

             ans++;

             now = a[i].y;

         }

     }

     cout<<ans<<endl;

     return ;

 }

 /*

 problem:yibentonglian10003

 date:2019/5/5

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn = 1e6+;

 struct node{

     int date,val;

 }a[maxn];

 bool visit[maxn];

 bool flag;

 int n,ans,s;

 inline bool cmp(node a,node b){

     return a.val > b.val;

 }

 int main(){

     cin>>n;

     for(int i = ;i <= n;i++)scanf("%d%d",&a[i].date,&a[i].val);

     memset(visit,false,sizeof(visit));

     sort(a+,a++n,cmp);

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

         if(a[i].date <= s)continue;

         flag = false;

         for(int j = a[i].date;j >= ;j--)

             if(visit[j] == false){

                 visit[j] = true;

                 ans += a[i].val;

                 flag = true;

                 break;

             }

         if(flag == false)s = a[i].date;

     }

     cout<<ans<<endl;

     return ;

 }

 /*

 problem:yibentonglian10004

 date:2019/5/5

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 const int maxn = 1e2+;

 int a[maxn],d[maxn],t[maxn],fish[maxn];

 int n,ans,h,sum,Max,position;

 int main(){

     cin>>n>>h;

     h *= ;

     for(int i = ;i <= n;i++)scanf("%d",&a[i]);

     for(int i = ;i <= n;i++)scanf("%d",&d[i]);

     for(int i = ,tmp;i < n;i++)scanf("%d",&tmp),t[i] = t[i-]+tmp;

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

         for(int j = ;j <= i;j++)fish[j] = a[j];

         int time = h - t[i-];

         sum = ;

         for(int j = ;j <= time;j++){

             Max = ;

             for(int k = ;k <= i;k++)

                 if(fish[k] > Max)Max = fish[k],position = k;

             if(Max == )break;

             fish[position] -= d[position];

             sum += Max;

         }

         ans = max(ans,sum);

     }

     cout<<ans<<endl;

     return ;

 }

 /*

 problem:yibentonglian10005

 date:2019/5/7

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int maxn = 1e6+;

 long long a[maxn],c[maxn];

 long long total,ave,ans;

 int n;

 int main(){

     cin>>n;

     for(int i = ;i <= n;i++)scanf("%d",&a[i]),total += a[i];

     ave = total/n;

     for(int i = ;i <= n;i++)c[i] = c[i-]+a[i]-ave;

     sort(c+,c++n);

     int mid = (n+)>>;

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

         ans += abs(c[mid]-c[i]);

     printf("%lld\n",ans);

     return ;

 }

 /*

 problem:yibentong10000

 date:2019/5/7

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int maxn = 1e5+;

 int a[maxn];

 int n,m,l,r;

 inline bool check(int x){

     int ans = ,sum = ;

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

         sum += a[i];

         if(sum > x)ans++,sum = a[i];

     }

     if(ans <= m)return true;

     return false;

 }

 int main(){

     cin>>n>>m;

     int Max = ,sum = ;

     for(int i = ;i <= n;i++)scanf("%d",&a[i]),Max = max(Max,a[i]),sum += a[i];

     l = Max,r = sum;

     while(l <= r){

         int mid = (l+r)>>;

         if(check(mid))r = mid-;

         else l = mid+;

     }

     cout<<l<<endl;

     return ;

 }

 /*

 problem:yibentong10001

 date:2019/5/7

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int maxn = 1e5+;

 int a[maxn];

 int n,m;

 inline bool check(int x){

     int ans = ;

     int cnt = a[]+x;

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

         if(a[i] < cnt)continue;

         ans++;

         cnt = a[i]+x;

     }

     return ans >= m;

 }

 int main(){

     cin>>n>>m;

     for(int i = ;i <= n;i++)scanf("%d",&a[i]);

     sort(a+,a++n);

     int l = ,r = a[n];

     while(l <= r){

         int mid = (l+r)>>;

         if(check(mid))l = mid+;

         else r = mid-;

     }

     cout<<r<<endl;

     return ;

 }

 /*

 problem:yibentong10002

 date:2019/5/11

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 #define ll long long

 const ll maxn = 5e1+;

 ll father[maxn],x[maxn],y[maxn];

 ll n,cnt,sum;

 struct edge{

     ll x,y,w;

 }e[maxn*maxn/];

 ll dist(ll i,ll j){

     return (abs(x[i]-x[j])+abs(y[i]-y[j])+)/;

 }

 ll cmp(edge a,edge b){

     return a.w < b.w;

 }

 ll find(ll x){

     if(father[x] == x)return x;

     else return father[x] = find(father[x]);

 }

 void Kruscal(){

     sort(e+,e++cnt,cmp);

     for(ll i = ;i <= cnt;i++)

         if(find(e[i].x) != find(e[i].y)){

             father[find(e[i].x)] = find(e[i].y);

             sum++;

             if(sum == n-){

                 printf("%lld\n",e[i].w);

                 break;

             }

         }

 }

 int main(){

     cin>>n;

     for(ll i = ;i <= n;i++)scanf("%d%d",&x[i],&y[i]);

     for(ll i = ;i <= n;i++)father[i] = i;

     for(ll i = ;i <= n;i++)

         for(ll j = i+;j <= n;j++){

             cnt++;

             e[cnt].x = i;

             e[cnt].y = j;

             e[cnt].w = dist(i,j);

         }

     Kruscal();

     return ;

 }

 /*

 problem:yibentong1000

 date:2019/5/11

 author:Lonely.Devil

 */

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 #define ll long long

 const ll maxn = 5e1+;

 struct point{

     ll x,y;

 }p[maxn];

 ll map[maxn][maxn];

 ll n,ans;

 inline ll Abs(ll x){

     if(x < )x = -x;

     return x;

 }

 inline ll Min(ll x,ll y){

     return x < y ? x : y;

 }

 inline ll Max(ll x,ll y){

     return x > y ? x : y;

 }

 inline ll dist(int i,int j){

     return (Abs(p[i].x-p[j].x)+Abs(p[i].y-p[j].y)+)/;

 }

 inline void Floyd(){

     for(ll k = ;k <= n;k++)

         for(ll i = ;i <= n;i++)

             for(ll j = ;j <= n;j++)

                 map[i][j] = min(map[i][j],max(map[k][j],map[i][k]));

 }

 int main(){

     cin>>n;

     for(ll i = ;i <= n;i++)scanf("%lld%lld",&p[i].x,&p[i].y);

     for(ll i = ;i <= n;i++)

         for(ll j = ;j <= n;j++)

             if(i == j)map[i][j] = ;

     for(ll i = ;i <= n;i++)

         for(ll j = i+;j <= n;j++)

             map[i][j] = map[j][i] = dist(i,j);

     Floyd();

     for(ll i = ;i <= n;i++)

         for(ll j = i+;j <= n;j++)

             if(ans < map[i][j])

                 ans = map[i][j];

     cout<<ans<<endl;

     return ;

 }