/*Rabbi Zidni Ilma*/

#include<bits/stdc++.h>
using namespace std;
#define   fastio    ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define   ll        long long
#define   scl(n)    scanf("%lld",&n)
#define   scll(n,m) scanf("%lld %lld",&n,&m)
#define   pb        push_back
#define   mp        make_pair
#define   frs       first
#define   scn       second
#define   mod       1000000007
#define   read      freopen("input.txt","r",stdin)
#define   write     freopen("output.txt","w",stdout)
#define   N         10000000

ll pow(ll x,ll y)
{
	ll i,pro=1;
	for(i=0;i<y;i++)
	pro*=x;
	
	return pro;
}

int main()
{
	//fastio;
    ll tc,t,n,m,i,j,k,mx,mn,c,x,y;
    
    scl(n);
    
    c=0;
    ll f=0;
    set<ll>st;
    for(i=2;i<=100000;i++)
    {
    	for(j=2;j<=34;j++)
    	{
    		x=pow(i,j);
    		if(x<=n)
    		st.insert(x);
    		else
    		{
    			f=1;
    			break;
			}
		}
	}
	
	ll sz=st.size();
	printf("%lld\n",n-sz);
}
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
#define rprintf(fmt, begin, end) do { const auto end_rp = (end); auto it_rp = (begin); for (bool sp_rp=0; it_rp!=end_rp; ++it_rp) { if (sp_rp) putchar(' '); else sp_rp = true; printf(fmt, *it_rp); } putchar('\n'); } while(0)

int N, M;
int A[1011], B[1011];
int dp[1011][1011];

void MAIN() {
    scanf("%d%d", &N, &M);
    REP (i, N) scanf("%d", A+i);
    REP (i, M) scanf("%d", B+i);

    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = M + N;

    REP (i, N+1) REP (j, M+1) {
	if (i < N && j < M) {
	    if (A[i] != B[j]) {
		amin(dp[i+1][j+1], dp[i][j] - 1);
	    } else {
		amin(dp[i+1][j+1], dp[i][j] - 2);
	    }
	}
	amin(dp[i][j+1], dp[i][j]);
	amin(dp[i+1][j], dp[i][j]);
    }


    int ans = dp[N][M];
    printf("%d\n", ans);

}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}

