#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200005;
const int INF = 1000000000;
int pre[MAX_N], nex[MAX_N];
int mark[MAX_N], dp[MAX_N];
int prefixSum[MAX_N];
deque<int> q;
int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b)
{
for (int i = 0; i < n; i++)
{
nex[i] = -1;
for (int j = 0; j < m && i + j < n; j++)
{
if (binary_search(b[j].begin(), b[j].end(), c[i + j]))
{
nex[i] = i + j;
}
else
{
break;
}
}
if (nex[i] - i + 1 == m)
{
mark[i] = true;
}
}
for (int i = 0; i < n; i++)
{
pre[i] = -1;
for (int j = i; j >= 0 && i - j < m; j--)
{
if (binary_search(b[m - (i - j + 1)].begin(), b[m - (i - j + 1)].end(), c[j]))
{
pre[i] = j;
}
else
{
break;
}
}
}
for (int i = 1; i < n; i++)
{
if (pre[i - 1] == -1 || nex[i] == -1)
{
continue;
}
if (nex[i] - pre[i - 1] + 1 < m)
{
continue;
}
prefixSum[pre[i - 1]]++;
prefixSum[nex[i] - m + 2]--;
}
for (int i = 0; i < n; i++)
{
if (prefixSum[i])
{
mark[i] = true;
}
prefixSum[i + 1] += prefixSum[i];
}
if (!mark[0] || !mark[n - m])
{
return -1;
}
dp[0] = 1;
q.push_back(0);
for (int i = 1; i <= n - m; i++)
{
if (mark[i])
{
while (q.size() && q.front() < i - m)
{
q.pop_front();
}
if (q.empty())
{
return -1;
}
dp[i] = dp[q.front()] + 1;
while (q.size() && dp[q.back()] >= dp[i])
{
q.pop_back();
}
q.push_back(i);
}
}
return dp[n - m];
}
