#include <iostream>
#include <memory.h>
#include <stdio.h>
using namespace std;
#define LL long long

LL dp[31][20000],n,m,row,zt;
LL num[10],pp[10];

// 状态  0----横放或者竖放的第三个格子 对下层没有影响
//       1----竖放的中间那个格子  对下一层有影响
//       2----竖放的第一个格子    对下两层有影响

void dfs(LL pos,LL status)
{
    if(pos==n)
    {
        dp[row+1][status]+=dp[row][zt];
        return;
    }
    if(num[pos]==0)  // 上层为0  这层可以横放或者成2
    {
        if(pos+2<n&&num[pos+1]==0&&num[pos+2]==0) dfs(pos+3,status);  // 横放
        dfs(pos+1,status+2*pp[pos]);
    }
    else if(num[pos]==1)     // 上层为1  这层为0
    {
        dfs(pos+1,status);
    }
    else      // 上层为2 这层为1
    {
        dfs(pos+1,status+pp[pos]);
    }
}

void change()
{
    LL now=zt,k=-1;
    memset(num,0,sizeof(num));
    if(now==0) return;
    while(now)
    {
        num[++k]=now%3;
        now/=3;
    }
}

int main()
{
    LL i,nmax;
    pp[0]=1;
    for(i=1;i<=9;i++) pp[i]=pp[i-1]*3;
    while(scanf("%lld%lld",&n,&m)&&(m||n))
    {
        if((m*n)%3!=0) {printf("0\n"); continue;}
        nmax=pp[n];      // 状态总数
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(row=0;row<=m-1;row++)
        {
            for(zt=0;zt<nmax;zt++)
            {
                if(dp[row][zt])
                {
                    change();
                    dfs(0,0);
                }
            }
        }
        printf("%lld\n",dp[m][0]);
    }
    return 0;
}

#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;

int dp[110],a[110],b[110],maxx,n,m;

int judge(int now)
{
    int i,j,k,tem;
    memset(dp,-1,sizeof(dp));
    for(j=0;j<=m;j++)
    {
        if(j*a[1]>now) break;
        tem=now-j*a[1];   // 第一个人完成j个任务1后还剩的时间
        tem=tem/b[1];     // 第一个人还能完成任务2的个数
        dp[j]=tem;
    }
    for(i=2;i<=n;i++)
    {
        for(j=m;j>=0;j--)    // 因为dp[]只用一维，所以类似完全背包 这里应该倒过来循环
        {
            for(k=0;k<=j;k++)
            {
                if(k*a[i]>now) break;
                tem=now-k*a[i];   // 第i个人完成k个任务1后还剩的时间
                tem=tem/b[i];     //  还能完成任务2的个数
                if(dp[j-k]!=-1&&dp[j-k]+tem>dp[j]) 
                    dp[j]=dp[j-k]+tem;
            }
        }
        if(dp[m]>=m) return 1;
    }
    return 0;
}

void solve()
{
    int l=0,r=maxx*2*m,ans=r,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(judge(mid)) 
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
}

int main()
{
    int t,i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        maxx=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",a+i,b+i);
            if(a[i]>maxx) maxx=a[i];
            if(b[i]>maxx) maxx=b[i];
        }
        solve();
    }
    return 0;
}

题意：n*m的网格，有些格子里可能有宝藏，若站在(x,y),每次只能向(x+1,y)或者(x,y+1)方向走，问最少要走几趟能将网格中的宝物收集完。
分析: 按题目的意思就是只能向右和向下走。如果将宝物的坐标按x轴来从小到大排(x轴相同的按y轴从小到大)，那么就可以只考虑y坐标了
，假设有两个位置i,j，i.x<=j.x,当i.y<=j.y时，才有可能收集完i后收集j,所以按x轴排序完后，问题就转化为用最少几个不降子序列可将y轴坐标序列全部涵盖。那就是最长(严格)递减子序列的长度了。

题意: 将字符串压缩到最短。压缩规则见题目。
分析: 这题我就是用了最原始的方法了。一段一段来压缩。即现在要压缩[i,j]这一段时，要保证任意一段长度比j-i+1小的压缩结果都已经得出来了，也就是按长度从小到大来dp。压缩[i,j]的方法有两种，一种压缩成"数字(字符串)"的形式，另一种是压缩成[i,k][k+1,j]的形式。比较一下，哪种短就选哪种了。

题意：问n个人的不同的排名方式有多少种，多个人可能处在同一个名次。
分析: 递推了。公式也很容易写出来。 f[i][j]表示有i个人，j个不同的名次(可能多个人在同一个名次)的方案数.
f[i][j]=f[i-1][j]*j+f[i-1][j-1]*j;  因为i个人排成j个档次可以在i-1个人j个档次的基础上随便找个档次(共有j个档次)加上第i个人，也可以在i-1个人j-1个档次的基础上让第i个人独立作为一个档次随意排，有j个位置。答案就是sigma{f[n][i] | i从1到n}。 这题要用大数。于是我的第一个java程序诞生了，乱搞查资料，debug了半天，终于写出来了，很丑的。自我鄙视一下。

题意：当任意两个卫星的距离小于等于25时，放置一个天线就可以同时接受到这两个卫星的信号。现在告诉n个卫星的位置，求最少需购买天线数量，同时需要保证，得到的信号值总和最大。信号值计算公式是Qx=100-|卫星的位置-天线的位置|。
分析：只要弄清楚了题意，就很容易发现这个题其实就是经典的村庄里建邮局的问题了，只不过这里要求每一段的范围在25以内。因为数据范围只有100，就没写什么优化了，直接上n^3的。
f[i][j]表示前i个卫星放j个天线所能得到的最大信号。 f[i][j]=max{f[k][j-1]+w[k+1][i]; | d[i]-d[k+1]<=25}

题意：好难表达...
分析：dp了，没什么好说的，dp[now]=min{dp[i]+dp[now-i],dp[i]+dp[now/i]且now%i==0,dp[i]+dp[j]且i^j==now;} 。不过转移的时候我的方法很暴力，不知道其他优秀的方法是怎么做的。 一些很明显的值的表达式可以预处理出来。

题意：给一些人的排列限制关系（比如x要排在y前面），求符合这些条件的排列总数。
分析: 这题自己没想出来，看了别人的题解。这句“我们想求一堆人的排列总数，它等于在这一堆人中减去每一个入度为 0 的人，剩下的人的排列总数的和。”就是这题的方法了。记忆化搜索写法。