OI XXXIII - pro

// https://szkopul.edu.pl/problemset/problem/up5Q4-UPi107yM0HUxKKoMno/site/?key=statement

// Prognoza pogody

#include <bits/stdc++.h>

#define ar std::array

constexpr int sizik = 10 * 1001;

int t[sizik], p[sizik];
int n, m;

namespace wz_test {

inline int z(int x, int q) {
    if (x >= q) x -= q;
    return x;
}

void solve() {
    int ans = INT32_MAX;

    for (int i = 0; i < m; i++) {
        int idx = 0, idx1 = i;
        int lc = 0;
        for (int j = 0; j < m; j++) {
            lc += (t[j] == p[z(idx1 + j, m)]);
        }
        ans = std::min(ans, m - lc);
        for (int j = 0; j < n - m; j++) {
            int y = (t[idx] == p[idx1]);
            idx++;
            idx1++;
            if (idx1 >= m) idx1 -= m;
            int x = (t[idx + m - 1] == p[z(idx1 + m - 1, m)]);
            if (y != x) {
                lc += x - y;
            }
            ans = std::min(ans, m - lc);
        }
    }

    std::cout << ans << '\n';

    return;
}

} // namespace wz_test

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

    std::cin >> n >> m;
    for (int i = 0; i < n; i++) {
        std::cin >> t[i];
    }
    for (int i = 0; i < m; i++) {
        std::cin >> p[i];
    }

    wz_test::solve();

    return 0;
}