Description

两个PACMAN吃豆豆。一开始的时候，PACMAN都在坐标原点的左下方，豆豆都在右上方。PACMAN走到豆豆处就会吃掉它。PACMAN行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。 请你帮这两个PACMAN计算一下，他们俩加起来最多能吃掉多少豆豆。

Input

第一行为一个整数N，表示豆豆的数目。 接下来 N 行，每行一对正整数，表示第i个豆豆的坐标。任意两个豆豆的坐标都不会重合。

Output

仅有一行包含一个整数，即两个PACMAN加起来最多能吃掉的豆豆数量

Sample Input

8

8 1

1 5

5 7

2 2

7 8

4 6

3 3

6 4

Sample Output

7

HINT

 

N < = 2000

暴力费用流显然会T。

然而可以常数优化一下就过了。

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define ren for(int i=first[x];i!=-1;i=next[i])using namespace std;const int BufferSize=1<<16;char buffer[BufferSize],*head,*tail;inline char Getchar() { if(head==tail) { int l=fread(buffer,1,BufferSize,stdin); tail=(head=buffer)+l; } return *head++;}inline int read() { int x=0,f=1;char c=Getchar(); for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1; for(;isdigit(c);c=Getchar()) x=x*10+c-'0'; return x*f;}const int maxn=4010;const int maxm=3000010;const int INF=1000000000;struct ZKW { int n,m,s,t,ans,cost; int first[maxn],next[maxm]; struct Edge { int from,to,flow,cost;}edges[maxm]; void init(int n) { this->n=n;m=0; memset(first,-1,sizeof(first)); } void AddEdge(int u,int v,int cap,int cost) { edges[m]=(Edge){u,v,cap,cost};next[m]=first[u];first[u]=m++; edges[m]=(Edge){v,u,0,-cost};next[m]=first[v];first[v]=m++; } int d[maxn],vis[maxn],inq[maxn]; int dfs(int x,int a) { if(x==t||!a) {ans+=a*cost;return a;} vis[x]=1;int flow=0,f; ren { Edge& e=edges[i]; if(!e.cost&&e.flow&&!vis[e.to]&&(f=dfs(e.to,min(a,e.flow)))) { e.flow-=f;edges[i^1].flow+=f; flow+=f;a-=f;if(!a) break; } } return flow; } int bfs() { queue
             
               Q;rep(i,1,n) d[i]=INF; d[t]=0;inq[t]=1;Q.push(t); while(!Q.empty()) { int x=Q.front();Q.pop();inq[x]=0; ren { Edge& e=edges[i^1]; if(e.flow&&d[e.from]>d[x]+e.cost) { d[e.from]=d[x]+e.cost; if(!inq[e.from]) inq[e.from]=1,Q.push(e.from); } } } rep(i,0,m-1) edges[i].cost+=d[edges[i].to]-d[edges[i].from]; cost+=d[s];return d[s]!=INF; } int solve(int s,int t) { this->s=s;this->t=t;ans=cost=0; while(bfs()) do memset(vis,0,sizeof(vis));while(dfs(s,INF)); return ans; }}sol;struct Point { int x,y; bool operator < (const Point& ths) const { return x
              
               
                =A[i].y) sol.AddEdge(i+n,j,2,0); if(A[j].y>=A[i].y) tmp=min(tmp,A[j].y); } } printf("%d\n",-sol.solve(S,t)); return 0;}