#include <bits/stdc++.h>
using namespace std;
int n,m,a[20][20],f[20][20],s[20];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    cin>>a[i][j];
    for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    for(int k=0;k<=j;k++)
    f[i][j]=max(f[i][j],f[i-1][j-k]+a[i][k]);
    cout<<f[n][m]<<endl;
    int j=m;
    for(int i=n;i;i--)
    for(int k=0;k<=j;k++)
    if(f[i][j]==f[i-1][j-k]+a[i][k])
    {
        s[i]=k;
        j-=k;
        break;
    }
    for(int i=1;i<=n;i++)
    cout<<i<<' '<<s[i]<<endl;
}

#include<bits/stdc++.h>
using namespace std;
int x,ji,sum;
int main()
{
    while(cin>>x&&x)
    {
        if(x==2)
        ji+=2,sum+=ji;
    else sum++,ji=0;
    }
    printf("%d",sum);
}

#include <bits/stdc++.h>
using namespace std;
int n,a[1005],sum;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=2;i<n;i++)
    if((a[i-1]<a[i]&&a[i]>a[i+1])||(a[i-1]>a[i]&&a[i]<a[i+1]))
    sum++;
    cout<<sum;
}

#include <bits/stdc++.h>
using namespace std;
int n,a1,a2,maxn;
int main()
{
    cin>>n;
    cin>>a1;
    for(int i=2;i<=n;i++)
    {
        cin>>a2;
        maxn=max(maxn,abs(a1-a2));
        a1=a2;
    }
    cout<<maxn;
}

#include <bits/stdc++.h>
using namespace std;
int n,a[105][105],l1,r1,l2,r2,sum;
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>l1>>r1>>l2>>r2;
        for(int i=l1;i<l2;i++)
        for(int j=r1;j<r2;j++)
        a[i][j]=1;
    }
    for(int i=0;i<=100;i++)
    for(int j=0;j<=100;j++)
    sum+=a[i][j];
    cout<<sum;
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,sum=0,l=0,a;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>a;
    if(a>l)
    sum+=a-l;
    l=a;
    }
    cout<<sum;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int a[505][505],n,x,y;
bool flag=1;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    cin>>a[i][j];
    cout<<a[0][0]<<' ';
    while(x!=n||y!=n)
    {
        if(flag)
        x--,y++;
        else x++,y--;
        if(x<0)
        {
            x=0;
            flag=!flag;
        }
        if(y<0)
        {
            y=0;
            flag=!flag;
        }
        if(x<n&&y<n)
            cout<<a[x][y]<<' ';
    }
}

#include <bits/stdc++.h>
using namespace std;
struct ss
{
    int l,r;
}a[100005];
int n,sum=1;
int cmp(ss a,ss b){return a.l<b.l;}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i].l>>a[i].r;
    sort(a+1,a+n+1,cmp);
    priority_queue<int,vector<int>,greater<int> >b;
    for(int i=1;i<=n;i++)
    {
        ss s=a[i];
        if(b.empty()||b.top()>=s.l)
        b.push(s.r);
    else{b.pop();
        b.push(s.r);}
    }
    printf("%d\n", b.size());
}

#include <bits/stdc++.h>
using namespace std;
long long n,a1,a2,maxn=-2e9,sum;
struct ss
{
    int w,s;
}a[500005];
int cmp(ss a,ss b){return a.w<b.w;}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a1>>a2;
        a[i]={a2+a1,a1};
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,sum-a[i].w+a[i].s);
        sum+=a[i].s;
    }
    cout<<maxn;
}

#include <bits/stdc++.h>
using namespace std;
string a,word[10]={"zero","one","two","three","four","five","six","seven","eight","nine"};
int sum,b[10],s;
int main()
{
    cin>>a;
    for(int i=0;i<a.size();i++)
    sum+=a[i]-'0';
    while(sum)
    {b[++s]=sum%10;
    sum/=10;}
    if(s==0)
    cout<<"zero";
    for(int i=s;i>=1;i--)
    cout<<word[b[i]]<<' ';
}