#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
namespace {
const int MXN = 200005, INF = 1e9;
int n, m, k;
vector<int> c;
vector<vector<int>> clr;
int cid[MXN], worker[MXN];
bitset<MXN> b;
int dp[MXN];
bool calc(int sr) {
auto check = [&](int x) -> bool {
FOR(i, 0, m) {
auto it = lower_bound(clr[(x + i) % m].begin(), clr[(x + i) % m].end(), c[sr + i]);
if (it == clr[(x + i) % m].end()) return false;
if (*it != c[sr + i]) return false;
}
return true;
};
FOR(x, 0, m) if (check(x)) return true;
return false;
}
int miku() {
FOR(i, m, n + 1) b[i] = calc(i - m);
deque<pii> dq;
dq.push_back(mp(0, 0));
FOR(i, 1, n + 1) {
if (!b[i]) dp[i] = INF;
else {
while (dq.front().sc < i - m) dq.pop_front();
dp[i] = dq.front().fs + 1;
}
while (dq.size() && dq.back().fs >= dp[i]) dq.pop_back();
dq.push_back(mp(dp[i], i));
}
return (dp[n] >= INF ? -1 : dp[n]);
}
}
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
::n = N;
::m = M;
::k = K;
::c = C;
::clr = B;
return miku();
}
