#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e6 + 10;
const ll INF = 2e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;
int n, m, k, C[MAXN];
vector<int> L[MAXN];
pair<int, int> W[2][MAXN];
ll dp[MAXN];
int minimumInstructions(
int N, int M, int K, std::vector<int> tC,
std::vector<int> tA, std::vector<std::vector<int>> tB) {
n = N, m = M, k = K;
for (int i = 0; i < n; i++) C[i] = tC[i];
for (int i = 0; i < m; i++)
for (int e : tB[i])
L[e].push_back(i);
set<pll> dp_st;
dp_st.insert({0, n});
for (int i = 0; i < MAXN; i++) W[n & 1][i] = {0, n};
for (int i = n - 1; i >= 0; i--) {
int ind = i & 1;
dp[i] = INF;
dp_st.erase({dp[i + m + 1], i + m + 1});
ll t = dp_st.begin() -> X;
for (int p : L[C[i]]) {
int l = 1, r = (p + 1) % m;
if (W[1 - ind][r].Y == i + 1) l = 1 + W[1 - ind][r].X;
if (l >= m) dp[i] = t + 1;
W[ind][p] = {l, i};
}
dp_st.insert({dp[i], i});
}
if (dp[0] >= INF) return -1;
return dp[0];
}
