#include using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() template inline bool chmax(A &a, B b) { if (a inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; } typedef unsigned long long ull; typedef long long ll; typedef pair pii; typedef pair pll; typedef pair P; const ll INF = 1ll<<29; const ll MOD = 1000000007; const double EPS = 1e-10; int n, m; string s, t; int dp[1001][1001]; int main() { cin >> n >> m >> s >> t; fill(dp[0], dp[1001], INF); dp[0][0] = 0; int ans = INF; REP(i, m) { REP(j, n) { // 変更 if (t[i] == s[j]) chmin(dp[i + 1][j + 1], dp[i][j]); else chmin(dp[i + 1][j + 1], dp[i][j] + 1); // 削除 chmin(dp[i][j + 1], dp[i][j] + 1); // 挿入 chmin(dp[i + 1][j], dp[i][j] + 1); } } REP(i, m + 1) REP(j, n + 1) chmin(ans, dp[i][j] + m - i + n - j); cout << ans << endl; return 0; }