Description

一条线上有栋楼,第栋楼有层,每层有1个价值为的物品.

可以花费1个单位时间完成以下3种移动:

1.在同一栋楼中向上或者向下走一层;

2.如果此刻在顶楼,可以通往1楼;

3.从当前楼移动到相邻楼的同层.如果相邻楼没有当前位置高，则会落到相邻楼的顶层。

初始时在第一栋楼的顶层，单位时间可以移动，拿去物品不需要时间，且一个物品被拿一次之后就会消失。

求能获得的最大的总价值.

Input

第一行两个正整数.

以下行每行两个整数表示和。

Output

输出一行一个整数表示最大的总价值。

Sample Input

3 3 2 1 1 5 3 4

Sample Output

14

HINT

Solution

枚举最远到达的那栋楼,然后贪心.

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define N 1000005using namespace std;typedef long long ll;struct house{ ll h,v,n;}a[N];int n,u;ll cnt[N],v[N],m,k,ans,sum,tmp;inline int read(){ int ret=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ ret=(ret<<1)+(ret<<3)+c-'0'; c=getchar(); } return ret;}inline ll rd(){ ll ret=0LL;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ ret=(ret<<1LL)+(ret<<3LL)+(ll)(c-'0'); c=getchar(); } return ret;}inline bool cmp(house x,house y){ if(x.v!=y.v) return x.v>y.v; return x.n
               
                m) n=(int)(m); for(int i=1;i<=n;++i){ a[i].h=rd();v[i]=a[i].v=rd();a[i].n=(ll)(i); } sort(a+1,a+1+n,cmp); for(int i=1;i<=n;++i){ ++cnt[a[i].n];--m; } for(int i=1;i<=n&&m;++i){ tmp=min(a[i].h-1LL,m); cnt[a[i].n]+=tmp;m-=tmp; } for(int i=1;i<=n;++i) ans+=cnt[i]*v[i]; for(u=1;u<=n;++u) if(cnt[a[u].n]!=a[u].h) break; sum=ans; for(int k=n;k>1;--k){ m=cnt[k];sum-=cnt[k]*v[k]; for(;u<=n;++u) if(a[u].n