#include <iostream>
using namespace std;
const int N=1e5+10;
int n;
int x;
int f[N][2];
int main(){
    cin>>n;
    cin>>x;
    f[0][0]=0;
    f[1][0]=0;
    f[1][1]=-x;
    f[0][1]=0xcf;
    for(int i=2;i<=n;i++){
        cin>>x;
        f[i][0]=max(f[i-1][0],f[i-1][1]+x);
        f[i][1]=max(f[i-2][0]-x,f[i-1][1]);
       // cout<<f[i][0]<<" " <<f[i][1]<<endl;
    }
    cout<<f[n][0];
}

#include <iostream>
using namespace std;
int n,m;

const int N=110;
int b[N][N];
int a[N][N];

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
           cin>>b[i][j];
           a[i][j]=1;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>b[i][j];
            if(b[i][j]==0){
                for(int k=0;k<m;k++){
                    a[i][k]=0;
                }
                for(int k=0;k<n;k++){
                    a[k][j]=0;
                }
            }
        }
    }
    int ant=1;

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
             int sum=0;
            if(b[i][j]){
                for(int k=0;k<m;k++){
                    sum+=a[i][k];
                }
                for(int k=0;k<n;k++){
                    sum+=a[k][j];
                }
                if(sum==0){
                    ant=0;
                }
            }
        }
    }
    if(ant){
        cout<<"YES"<<endl;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cout<<a[i][j]<<" ";
            }
            cout<<endl;
        }
    }else{
        cout<<"NO"<<endl;
    }

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,k;
const int N=1e5+10;
int f[N][110][2];
int a[N];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
     memset(f,0xcf,sizeof f);//f[0][0][1]不存在定义为-inf
     for(int i=0;i<=n;i++)f[i][0][0]=0;//从零开始没有买没有交易为0
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+a[i]);
            f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-a[i]);
        }
    }
    int res=0;
    for(int i=1;i<=k;i++)res=max(res,f[n][i][0]);
    cout<<res<<endl;
    return 0;
}

#include <iostream>
using namespace std;
int T;
int n;
int w;
const int N=1e5+10;
int f[N];
int main(){
    cin>>T;
    while(T--){
        int a;//数组？累赘罢了
        cin>>n;
        for(int i=2;i<=n+1;i++){
            cin>>a;
            f[i]=max(f[i-1],f[i-2]+a);
        }
        cout<<f[n+1]<<endl;
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define v first  
#define w second

using namespace std;
typedef pair<int,int> PII;
const int N=32010,M=70;
int n,m;
vector<PII> son[M];
PII fa[M];
int f[M][N];
int main(){
    cin>>n>>m;
     int v,p,q;
    for(int i=1;i<=m;i++){
         cin>>v>>p>>q;
         if(!q)fa[i]={v,v*p};
         else son[q].push_back({v,v*p});
    }
    for(int i=1;i<=m;i++){//在第i组在j体积下已经选择第i主件的最大值
        if(fa[i].v){
            for(int j=fa[i].v;j<=n;j++){
                f[i][j]=f[i-1][j-fa[i].v]+fa[i].w;//更新当前第i组的状态（因为从后往前所有不需要用max更新）
            }
            for(int k=0;k<son[i].size();k++){
                for(int j=n;j>=son[i][k].v;j--){
                    if(f[i][j-son[i][k].v]>0){
                        f[i][j]=max(f[i][j],f[i][j-son[i][k].v]+son[i][k].w);//在附件中选择一个最优
                    }
                }
            }
        }
        for(int j=0;j<=n;j++)
        f[i][j]=max(f[i][j],f[i-1][j]);//不是主件则将上一组主件更新

    }
    cout<<f[m][n]<<endl;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=110,M=10010;
int T;
int f[M];
struct Stone{
    int s,e,l;
    bool operator<(const Stone&x)const{
        return s*x.l<l*x.s;
    }
}stones[N];
int n;
int main(){
    cin>>T;
    int cnt=0;
    while(T--){
        cnt++;
      cin>>n;
      memset(f, 0xcf, sizeof f);
     f[0]=0;
      int sum_s=0;
      for(int i=1;i<=n;i++){
          int s,e,l;
          cin>>s>>e>>l;
          stones[i]={s,e,l};
          sum_s+=s;
      }
      sort(stones+1,stones+n+1);
      for(int i=1;i<=n;i++){
          int s=stones[i].s;
          int e=stones[i].e;
          int l=stones[i].l;
          for(int j=sum_s;j>=stones[i].s;j--){

              f[j]=max(f[j],f[j-s]+max(0,e-l*(j-s)));
          }
      } 
      int ans=0;
      for(int i=1;i<=sum_s;i++){
          ans=max(ans,f[i]);
      }
      cout<<"Case #"<<cnt<<": "<<ans<<endl;;
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N=1010;
int f[N][N];
int v[N],w[N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=n;i>=1;i--){//反推是为了让同样的价值体积在更早处不然从后往前会一直往后更新，具体方案的字典序不是最优

        for(int j=1;j<=m;j++){
            f[i][j]=f[i+1][j];
            if(j>=v[i]){
            f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
            }            
        }
    }
    for(int i=1,j=m;i<=n;i++){

        if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i]){
            cout<<i<<" ";
            j-=v[i];
        }
    }
    return 0;
}

#include<iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=110;
int n,m;
int e[N],ne[N],h[N],idx;
int v[N],w[N],f[N][N];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u){
    for(int i=h[u];i!=-1;i=ne[i]){
        int son=e[i];
        dfs(e[i]);
        for(int j=m-v[u];j>=0;j--){
            for(int k=0;k<=j;k++){
                 f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);    
            }
        }
    }
    for(int i=m;i>=v[u];i--){
        f[u][i]=f[u][i-v[u]]+w[u];
    }//加上父节点
    for(int i=0;i<v[u];i++){
        f[u][i]=0;
    }
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    int root;
     int p;
    for(int i=1;i<=n;i++){

        cin>>v[i]>>w[i]>>p;
        if(p==-1)root=i;
        else add(p,i);
    }
    dfs(root);
    cout<<f[root][m]<<endl;
    return 0;
}

#include<iostream>
using namespace std;
const int N=1010;
int f[N];
int g[N];
int n,m;
int mod=1e9+7;
int main(){
    cin>>n>>m;
    int v,w;
    f[0]=0;
    for(int i=0;i<=m;i++)g[i]=1;
    for(int i=1;i<=n;i++){
        cin>>v>>w;
        for(int j=m;j>=v;j--){
            int maxv=max(f[j],f[j-v]+w);
            int s=0;
            if(maxv==f[j])s+=g[j];
            if(maxv==f[j-v]+w)s=(s+g[j-v])%mod;
            g[j]=s;
            f[j]=maxv;
        }
    }
    cout<<g[m]<<endl;
    return 0;
}