#include "paint.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
const int INF = 1e5+1;
int minimumInstructions(int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B)
{
n = N; m = M; k = K;
vector<bool> p(n);
for (int y=0; y<=n-m; y++)
{
bool valy = false;
for (int x=0; x<m && !valy; x++)
{
//checking
bool valx = true;
for (int l=0; l<m && valx; l++)
{
int segment = y+l;
int painter = (x+l)%m;
bool match = false;
for (auto u: B[painter]) {if (C[segment] == u) match = true;}
if (!match) valx = false;
//if (y == 0 && x == 1)
//{
// cout<<segment<<" "<<painter<<"\n";
// for (auto u: B[painter]) {cout<<u<<" ";} cout<<"\n";
//}
}
if (valx) {valy = true;}
}
if (valy) {p[y] = true; continue;}
}
//for (auto &u: B) {for (auto &v: u) {cout<<v<<" ";} cout<<'\n';}
//for (auto u: p) {cout<<u<<" ";} cout<<'\n';
vector<int> left(n);
if (p[0]) left[0] = 0;
else left[0] = -INF;
for (int i=1; i<n; i++)
{
if (p[i]) left[i] = i;
else left[i] = left[i-1];
}
//for (auto u: left) {cout<<u<<" ";} cout<<"\n";
vector<int> g(n);
for (int i=n-1; i>=0; i--)
{
//cout<<left[i]+m-1<<"\n";
if (left[i] == -INF || left[i]+m-1 < i) {g[i] = INF;}
else if (left[i] != -INF && left[i]+m >= n) {g[i] = 1;}
else if (left[i] != -INF) {g[i] = 1 + g[i+m];}
}
//for (auto u: g) {cout<<u<<" ";} cout<<"\n";
return ((g[0] >= INF) ? -1 : g[0]);
}
