#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <stack>#include <queue>#include <vector>#include <map>#include <string>#include <iostream>using namespace std;int a[1111],b[1111];int c[1111111],c1[1111111];int Max(int gao,int gao1){    return gao>gao1?gao:gao1;}int ab(int x){    return x>0?x:-x;}int main(){    int n ;    while(cin>>n,n>=0){        int sum =0 ;        for(int i =0 ;i<n;i++){            scanf("%d%d",&a[i],&b[i]);            sum+=a[i]*b[i];        }        int minl=0;int minr=0;        for(int i= 0;i<=sum;i++)            c[i]=c1[i]=0;        c[0]=1;        for(int i= 0;i<n;i++){            for(int j=0;j<=b[i];j++)                for(int k=0 ;k+j*a[i]<=sum;k++)                c1[k+j*a[i]]+=c[k];            for(int j=0;j<=sum;j++)                c[j]=c1[j];        }        int Min=0xfffffff;        for(int i= 0 ;i<=sum;i++) if(c[i]){            int gg= ab(i*2 - sum);            if(gg<Min){                Min=gg;minl=Max(i,sum-i);minr=sum-minl;            }        }        printf("%d %d\n",minl,minr);    }    return 0;}

#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <stack>#include <queue>#include <vector>#include <map>#include <string>#include <iostream>using namespace std;int a[300*19];int b[300*19];int c[300*19];int c1[300*19];int main(){    int n;    while(scanf("%d",&n),n){        for(int i=1;i<=17;i++){            a[i]=i*i; b[i]=n/a[i];        }        for(int i= 0;i<=n;i++) c[i]=c1[i]=0;        c[0]=1;        for(int i= 1;i<=17;i++){            for(int j=0;j<=b[i];j++)            for(int k= 0;k+j*a[i]<=n;k++){                c1[k+j*a[i]]+=c[k];            }            for(int k=0;k<=n;k++)                c[k]=c1[k],c1[k]=0;        }        printf("%d\n",c[n]);    }    return 0;}

#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <stack>#include <queue>#include <vector>#include <map>#include <string>#include <iostream>using namespace std;int cnt[100];int val[100];int c[50*10*10];int c1[50*10*10];int main(){    int t,n,k;    scanf("%d",&t);    while(t--){        int sum=0;        scanf("%d%d",&n,&k);        for(int i= 0;i<k;i++)            scanf("%d%d",&val[i],&cnt[i]),sum+=val[i]*cnt[i];        for(int i=0;i<=sum;i++)            c1[i]=c[i]=0;        c[0]=1;        for(int i= 0;i<k;i++){            for(int j= 0;j<=cnt[i];j++){                for(int g=0;g+j*val[i]<=sum;g++)                    c1[g+j*val[i]]+=c[g];            }            for(int j=0;j<=sum;j++)                c[j]=c1[j],c1[j]=0;        }        printf("%d\n",c[n]);    }    return 0;}

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;LL val[1000];LL cnt[1000];LL c[11111],c1[11111];int main(){    LL t;    scanf("%I64d",&t);    for(LL i= 0;i<26;i++) val[i]=i+1;    while(t--){        LL sum=0;        for(LL i= 0;i<26;i++)        scanf("%I64d",&cnt[i]),sum+=cnt[i]*val[i];        for(LL i=0;i<=sum;i++)            c[i]=c1[i]=0;        c[0]=1;        for(LL i= 0;i<26;i++){            for(LL j=0;j<=cnt[i];j++)                for(LL k=0;k+j*val[i]<=sum;k++)                c1[k+j*val[i]]+=c[k];            for(LL j=0;j<=sum;j++)                c[j]=c1[j],c1[j]=0;        }        LL ans=0;        for(LL i=1;i<=50;i++)            ans+=c[i];        printf("%I64d\n",ans);    }    return 0;}

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;int val[11111],cnt[111111];int c[222222],c1[222222];const int mod=10000;int main(){    int n;    while(scanf("%d",&n),n){        int sum=0;        for(int i=0;i<n;i++)            scanf("%d%d",&val[i],&cnt[i]),sum+=val[i]*cnt[i];        if(sum%3){            printf("sorry\n");continue;        }        for(int i=0;i<=sum;i++)            c[i]=c1[i]=0;        c[0]=1;        for(int i=0;i<n;i++){            for(int j=0;j<=cnt[i];j++)                for(int k=0;k+j*val[i]<=sum;k++)                    c1[k+j*val[i]] += c[k];            for(int j=0;j<=sum;j++)                c[j]=c1[j],c1[j]=0,c[j]%=mod;        }        if(c[sum/3]) cout<<c[sum/3]<<endl;        else cout<<"sorry"<<endl;    }    return 0;}

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;int c[1000],c1[1000];int a[10000],b[10000];int main(){    int n,m;    while(scanf("%d%d",&n,&m)!=EOF){        for(int i=0;i<n;i++){            scanf("%d%d",&a[i],&b[i]);        }        for(int i=0;i<=m;i++) c[i]=c1[i]=0;        c[0]=1;        for(int i=0;i<n;i++){            for(int j=a[i];j<=b[i];j++){                for(int k=0;k+j<=m;k++)                c1[k+j]+=c[k];            }            for(int j=0;j<=m;j++)                c[j]=c1[j],c1[j]=0;        }        printf("%d\n",c[m]);    }    return 0;}