#include "paint.h"
#include <vector>
#include <queue>
#include <stack>
#define mp make_pair
using namespace std;
const int INF = 1e6;
typedef pair<int, int> pi;
// 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);
vector<int> inv(K);
for (int i = 0; i < N; i++) {
inv[B[i][0]] = i;
}
queue<pi> res;
res.push(mp(0, 0));
for (int i = 0; i <= N - M; i++) {
while (!res.empty() && res.front().first < i) {
res.pop();
}
if (res.empty()) {
return -1;
}
int p = res.front().second;
int s = inv[C[i]];
bool leave = false;
for (int l = 0; l < M && !leave; l++) {
int v = (l + s) % M;
if (B[v][0] != C[l + i]) {
i = i + l;
leave = true;
break;
}
}
if (leave) {
continue;
}
res.push(mp(i, p + 1));
}
while (!res.empty() && res.front().first < N) {
res.pop();
}
if (res.empty()) {
return -1;
}
else {
return res.front().second;
}
}
