#include "paint.h"
#include <vector>
using namespace std;
const int INF = 1e6;
// How few instructions to paint the first i days?
vector<int> dp;
vector<bool> doable;
bool find(vector<int>& v, int a) {
int p = lower_bound(v.begin(), v.end(), a) - v.begin();
if (p == v.size()) {
return false;
}
return v[p] == a;
}
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
dp.assign(N + 1, INF);
doable.assign(N, false);
dp[0] = 0;
for (int s = 0; s < M; s++) {
int fail = -1;
for (int i = 0; i < N; i++) {
int v = (s + i) % M;
if (find(B[v], C[i]) == false) {
fail = i;
}
if (i - fail >= M) {
doable[i - M + 1] = true;
}
}
}
for (int i = 0; i <= N - M; i++) {
if (doable[i]) {
for (int j = 1; j <= M; j++) {
dp[i + j] = min(dp[i + j], dp[i] + 1);
}
}
}
if (dp[N] == INF) {
return -1;
}
return dp[N];
}
