#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
const int N = 3e5 + 20;
vector<int> vt[N];
int col[N], last[N], dp[N];
bool have[N];
vector<int> vt1, vt2;
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B)
{
int n = N, m = M, k = K;
for (int i = 0; i < n; i++)
{
col[i] = C[i];
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < A[i]; j++)
{
int c = B[i][j];
vt[c].push_back(i);
}
}
for (int i = 0; i < k; i++)
{
last[i] = -2;
}
for (int i = 0; i < n; i++)
{
vt1.clear(); vt2.clear();
for (int j : vt[col[i]])
{
int j2 = j - 1;
if (j2 < 0) j2 = m - 1;
if (last[j2] == i - 1)
{
vt1.push_back(j);
}
else
{
vt2.push_back(j);
}
}
for (int j : vt1)
{
int j2 = j - 1;
if (j2 < 0) j2 = m - 1;
dp[j] = min(dp[j2] + 1, m);
last[j] = i;
}
for (int j : vt2)
{
dp[j] = 1;
last[j] = i;
}
for (int j : vt[col[i]])
{
if (dp[j] == m) have[i - m + 1] = true;
}
}
int i = 0, j = 0;
int ans = 0;
while (i < n)
{
int ff = -1;
for (int kk = i; kk >= j; kk--)
{
if (have[kk])
{
ff = kk;
break;
}
}
if (ff == -1) return -1;
ans++;
j = i + 1;
i = m + ff;
}
return ans;
}
