LISLCS

#define task "LISLCS"
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 5e3 + 5;
int m, n;
int a[N], b[N];

void Read()
{
    cin >> m >> n;

    for (int i = 1; i <= m; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> b[i];
}

int lcs[N][N], f[2][N][N];

void Sub_2()
{
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (a[i] == b[j])
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
            else
                lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
        }

        int p = i & 1, np = !(i & 1);

        for (int j = 1; j <= n; ++j)
            if (a[i] == b[j])
            {

                for (int t = 1, maxn = 0; t <= 500; ++t)
                {
                    f[p][j][t] = 0;

                    f[p][j][t] = max(f[p][j][t], f[np][j - 1][t]);

                    if (lcs[i][j] == lcs[i][j - 1])
                        f[p][j][t] = max(f[p][j][t], f[p][j - 1][t]);
                    if (lcs[i][j] == lcs[i - 1][j])
                        f[p][j][t] = max(f[p][j][t], f[np][j][t]);

                    if (t < a[i])
                        maxn = max(maxn, f[np][j - 1][t]);
                    else if (t == a[i])
                        f[p][j][t] = max(f[p][j][t], maxn + 1);
                }
            }
            else
            {
                for (int t = 1; t <= 500; ++t)
                {
                    f[p][j][t] = 0;
                    if (lcs[i][j] == lcs[i][j - 1])
                        f[p][j][t] = max(f[p][j][t], f[p][j - 1][t]);
                    if (lcs[i][j] == lcs[i - 1][j])
                        f[p][j][t] = max(f[p][j][t], f[np][j][t]);
                }
            }
    }

    int ans(0);

    for (int t = 1; t <= 500; ++t)
        ans = max(ans, f[m & 1][n][t]);

    cout << ans;
}

int nex[N][N];

void Min(int &x, int y)
{
    if (x > y)
        x = y;
}

void Sub_3()
{
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (a[i] == b[j])
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
            else
                lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
        }
    }

    fill_n(&f[0][0][0], 2 * N * N, n + 1);
    fill_n(&nex[0][0], N * N, n + 1);

    for (int i = n; i; --i)
    {
        for (int j = 0; j <= 500; ++j)
            nex[j][i] = nex[j][i + 1];
        nex[b[i]][i] = i;
    }

    f[0][0][0] = 0;

    for (int i = 1; i <= m; ++i)
    {
        int p = i & 1;
        int np = !p;

        f[p][0][0] = nex[a[i]][1];

        for (int j = 1; j <= i; ++j)
            for (int t = 0, maxn = n + 1; t <= 500; ++t)
            {
                f[p][j][t] = n + 1;

                if (f[np][j][t] != n + 1 && lcs[i][nex[a[i]][f[np][j][t] + 1]] == lcs[i - 1][f[np][j][t]] + 1)
                    Min(f[p][j][t], nex[a[i]][f[np][j][t] + 1]);
                if (lcs[i][f[np][j][t]] == lcs[i - 1][f[np][j][t]])
                    Min(f[p][j][t], f[np][j][t]);

                if (j)
                {
                    if (f[np][j - 1][t] != n + 1 && lcs[i][nex[a[i]][f[np][j - 1][t] + 1]] == lcs[i - 1][f[np][j - 1][t]] + 1 && t < a[i])
                        maxn = min(maxn, nex[a[i]][f[np][j - 1][t] + 1]);
                    else if (t == a[i])
                        Min(f[p][j][t], maxn);
                }

                if (f[p][j][t] != n + 1)
                    cerr << i << " " << j << " " << t << ": " << f[p][j][t] << "\n";
            }
    }

    for (int i = m; ~i; --i)
        for (int j = 500; ~j; --j)
            if (f[m & 1][i][j] != n + 1)
            {
                cout << i;
                return;
            }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();

    if (m <= 500 && *max_element(a + 1, a + m + 1) <= 500 && *max_element(b + 1, b + n + 1) <= 500)
    {
        Sub_2();
    }
}

/*
15 20
8 4 4 9 4 8 7 9 4 9 3 1 7 3 5
8 8 8 4 5 4 6 4 5 6 3 7 1 3 2 9 1 9 9 4

10 13
17 11 4 14 17 19 18 15 1 19
18 4 5 12 12 11 18 19 18 1 4 7 16

268 212
8 7 9 2 1 7 9 3 6 5 3 7 7 5 1 8 3 3 6 3 3 3 1 6 8 4 2 4 8 4 1 5 7 1 8 8 9 2 10 2 3 6 9 1 10 9 5 4 1 10 10 1 10 7 7 6 1 5 4 8 7 10 3 10 5 5 6 6 9 1 10 8 4 3 7 1 6 7 7 1 8 7 2 2 9 3 7 8 7 7 8 4 2 3 6 3 7 8 7 1 3 3 4 7 8 7 3 10 1 8 10 3 5 2 3 4 9 10 7 8 1 5 3 10 7 7 4 3 6 5 7 9 1 8 7 6 9 9 10 10 10 4 7 6 5 5 8 7 2 5 8 1 9 9 10 8 2 1 4 8 2 5 5 2 6 2 3 10 8 4 2 7 6 10 2 10 10 10 5 10 8 1 2 6 6 10 5 7 4 6 2 10 8 1 6 1 4 8 3 3 2 4 2 8 4 1 7 8 8 3 1 8 5 2 6 2 8 8 10 6 8 3 10 7 6 3 5 4 10 7 3 6 7 4 3 4 9 2 5 4 6 10 5 10 9 1 8 10 6 8 5 6 5 3 6 5 6 4 5 2 7 6 10 10 9 9 1 6
7 8 2 3 1 8 8 4 8 2 2 7 7 10 9 10 9 5 1 9 7 1 10 7 4 10 1 10 6 4 3 3 2 4 6 9 4 5 1 8 9 4 7 4 7 6 1 10 10 3 6 5 8 2 4 7 8 2 1 2 1 2 4 8 1 4 8 4 2 7 9 4 7 3 8 7 2 8 1 7 7 3 4 7 8 4 2 1 5 7 9 1 5 10 3 2 4 10 10 8 1 6 10 4 8 7 7 3 2 8 10 9 3 6 8 5 3 9 8 9 6 2 3 2 8 5 2 6 9 8 10 3 8 10 8 7 3 9 3 5 5 5 8 10 3 9 2 5 2 1 1 9 1 8 9 3 7 10 10 4 9 8 10 3 4 5 9 10 6 2 4 3 7 8 9 7 1 3 1 8 4 3 7 4 5 1 4 2 10 4 9 8 9 7 4 3 4 7 6 7 2 1 5 8 8 5 10 1 2 1 6 9
*/