#include "paint.h"
#include <cstring>
#include <vector>
const int N = 20000, K = 100000, M = 2000;
int min(int a, int b) { return a < b ? a : b; }
int minimumInstructions(int n, int m, int k, std::vector<int> aa, std::vector<int> kk, std::vector<std::vector<int>> aaa) {
int h, i, i_, j, ans;
if (n <= 500) {
static int jj[K][M], ll[K], len[N][M];
static char can[N];
for (j = 0; j < m; j++)
for (h = 0; h < kk[j]; h++) {
int a = aaa[j][h];
jj[a][ll[a]++] = j;
}
for (i = 0; i < n; i++) {
int a = aa[i];
for (h = 0; h < ll[a]; h++)
len[i][(jj[a][h] - i % m + m) % m] = 1;
}
for (j = 0; j < m; j++)
for (i = n - 2; i >= 0; i--)
if (len[i][j])
len[i][j] += len[i + 1][j];
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if (len[i][j] >= m) {
can[i] = 1;
break;
}
if (!can[0])
return -1;
i = 0, ans = 1;
while (i + m < n) {
for (i_ = min(i + m, n - 1); i_ > i; i_--)
if (can[i_])
break;
if (i_ == i)
return -1;
i = i_, ans++;
}
return ans;
} else {
static int jj[K];
memset(jj, -1, k * sizeof *jj);
for (j = 0; j < m; j++)
for (h = 0; h < kk[j]; h++)
jj[aaa[j][h]] = j;
for (i = 0; i < n; i++)
if (jj[aa[i]] == -1)
return -1;
ans = 0;
for (i = 0; i < n; i = i_) {
i_ = i + 1;
while (i_ < n && (jj[aa[i_ - 1]] + 1) % m == jj[aa[i_]])
i_++;
if (i_ - i < m)
return -1;
ans += (i_ - i + m - 1) / m;
}
}
return ans;
}
