#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;
int n,m;
int h[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0},dy[4] = {0, 1, 0, -1};


int dfs(int x,int y) {
    if(f[x][y] != -1) return f[x][y];

    f[x][y] = 1;
    for(int i = 0;i < 4;i++) {
        int a = x + dx[i],b = y + dy[i];
        if(a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
            f[x][y] = max(f[x][y],dfs(a,b) + 1);
    }
    return f[x][y];    
}

int main() {
    cin >> n >> m;

    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            cin >> h[i][j];

    memset(f,-1,sizeof f);

    int res = 0;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            res = max(res,dfs(i,j));

    cout << res << endl;

    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int get(vector<int> nums,int l,int r) {
    int res = 0;
    for(int i = l;i >= r;i--) res = res * 10 + nums[i];
    return res;
}

int power(int x) {
    int res = 1;
    while(x--) res *= 10;
    return res;
}

int count(int n,int x) {
    if(!n) return 0;

    vector<int> nums;
    while(n) {
        nums.push_back(n % 10);
        n /= 10;
    }
    n = nums.size();

    int res = 0;
    for(int i = n - 1 - !x;i >= 0;i--) {
        if(i < n - 1) {
            res += get(nums,n - 1,i + 1) * power(i);
            if(!x) res -= power(i);
        }
        if(x == nums[i]) res += get(nums,i - 1,0) + 1;
        else if(x < nums[i]) res += power(i);
    }
    return res;
}

int main() {
    int a,b;
    while(cin >> a >> b,a || b) {
        if(a > b) swap(a,b);
        for(int i = 0;i < 10;i++)
            cout << count(b,i) - count(a - 1,i) << " ";
        cout << endl;
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 6010;
int happy[N];
int h[N],e[N],ne[N],idx;
int f[N][2];
bool has_father[N];

void add(int a,int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dfs(int u) {
    f[u][1] = happy[u];

    for(int i = h[u];i != -1;i = ne[i]) {
        int j = e[i];
        dfs(j);

        f[u][0] += max(f[j][0],f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main() {
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> happy[i];

    memset(h,-1, sizeof h);

    for(int i = 0;i < n - 1;i++) {
        int a,b;
        cin >> a >> b;
        add(b,a);
        has_father[a] = true;
    }

    int root = 1;
    while(has_father[root]) root++;

    dfs(root);

    cout << max(f[root][0],f[root][1]) << endl;

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 20,M = 1 << N;
int n;
int w[N][N];
//f[i][j]集合：所有的 从0到j的所有路径
//属性：最小值
int f[M][N];

int main() {
    cin >> n;

    for(int i = 0;i < n;i++)
        for(int j = 0;j < n;j++)
            cin >> w[i][j];

    memset(f,0x3f,sizeof f);
    f[0][0] = 0;

    for(int i = 0;i < 1 << n;i++)
        for(int j = 1;j < n;j++)
            if(i >> j & 1)
                for(int k = 1;k < n;k++)
                    if(i >> k & 1)
                        f[i][j] = min(f[i][j],f[i -(1 << j)][k] + w[k][j]);

    cout << f[(1 << n) - 1][n - 1] << endl;

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n,m;
int p[N];

int find(int x) {
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m;
    for(int i = 1;i <= n;i++) p[i] = i;

    while(m--) {
        char op[2];
        int a,b;
        scanf("%s",op);
        if(*op == 'M') {
            cin >> a >> b;
            p[find(a)] = find(b);
        }
        else {
            cin >> a >> b;
            if(p[find(a)] == p[find(b)]) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;
int n,m;
int s[N],v[N][N],w[N][N];
int f[N];

int main() {
    cin >> n >> m;

    for(int i = 1;i <= n;i++) {
        cin >> s[i];
        for(int j = 0;j < s[i];j++)
            cin >> v[i][j] >> w[i][j];
    }

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

    cout << f[m] << endl;

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int n,m;
int v[N],w[N];
int f[N];

int main() {
    cin >> n >> m;

    for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];

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

    cout << f[m] << endl;

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int n,m;
int v[N],w[N];
int f[N];

int main() {
    cin >> n >> m;

    for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];

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

    cout << f[m] << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 12,M = 1 << N;
int n,m;
long long f[N][M];
bool st[M];

int main() {
    while(cin >> n >> m,n | m) {
        //预处理所以的状态
        for(int i = 0;i < 1 << n;i++) {
            int cnt = 0;
            st[i] = true;
            for(int j = 0;j < n;j++)
                if(i >> j & 1) {
                    if(cnt & 1) st[i] = false;
                    cnt = 0;
                }
                else cnt++;
            if(cnt & 1) st[i] = false;
        }

        memset(f,0,sizeof f);
        f[0][0] = 1;

        //m列,第一列的摆法只有一种
        //第m + 1列,也就是下标为m的列表示前面的所有的方法数
        for(int i = 1;i <= m;i++)
            for(int j = 0;j < 1 << n;j++)
                for(int k = 0;k < 1 << n;k++)
                    if((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];
        cout << f[m][0] << endl;
    }

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010,mod = 1e9 + 7;
int n;
//集合：所有的 前i个数,和恰好为j的方法的集合
//属性：个数
int f[N];

int main() {
    cin >> n;

    f[0] = 1;
    for(int i = 1;i <= n;i++)
        for(int j = i;j <= n;j++)
            f[j] = (f[j] + f[j - i]) % mod;

    cout << f[n] << endl;

    return 0;
}