#line 1 "paper.cpp"
#include <bits/stdc++.h>
#line 3 "library2/utility/len.hpp"
template <class Container> int len(const Container&c){
return static_cast<int>(std::size(c));
}
#line 5 "library2/utility/lwb.hpp"
template <class Container, class T> constexpr int lwb(const Container &c, const T &val) {
return static_cast<int>(std::distance(c.cbegin(), std::lower_bound(c.cbegin(), c.cend(), val)));
}
#line 3 "library2/utility/rep.hpp"
class Range {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
++itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr Range(const int f, const int l) noexcept
: first(f), last(std::max(f, l)) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr Range rep(const int l, const int r) noexcept {
return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
return Range(0, n);
}
#line 3 "library2/utility/revrep.hpp"
class ReversedRange {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
--itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr ReversedRange(const int f, const int l) noexcept
: first(l - 1), last(std::min(f, l) - 1) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr ReversedRange revrep(const int l, const int r) noexcept {
return ReversedRange(l, r);
}
constexpr ReversedRange revrep(const int n) noexcept {
return ReversedRange(0, n);
}
#line 7 "paper.cpp"
// #include "paint.h"
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A,
std::vector<std::vector<int>> B) {
auto make_table = [&]() {
const int s = N - M + 1;
std::vector<std::vector<int>> likeds(K);
for (const int i : rep(M)) {
for (const int j : B[i]) {
likeds[j].push_back(i);
}
}
std::vector<std::vector<bool>> B2(M, std::vector<bool>(K));
for (const int i : rep(M)) {
for (const int j : B[i]) {
B2[i][j] = true;
}
}
std::vector<bool> ret(s);
for (const int f : rep(M)) {
std::vector<int> bads;
for (const int i : rep(N)) {
if (not B2[(f + i) % M][C[i]]) {
bads.push_back(i);
}
}
for (const int j : rep(s)) {
const auto itr = std::lower_bound(bads.begin(), bads.end(), j);
if (itr == bads.end() or *itr >= j + M) {
ret[j] = true;
}
}
}
return ret;
};
auto calc_answer = [M](std::vector<bool> d) {
const int s = len(d);
std::vector<int> r_min(s);
r_min[s - 1] = d[s - 1] ? s - 1 : s;
for (const int i : revrep(s - 1)) {
r_min[i] = d[i] ? i : r_min[i + 1];
}
if (r_min[s - 1] == s) {
return -1;
}
int answer = 1, now = s - 1;
while (now != 0) {
const int nxt = r_min[std::max(0, now - M)];
if (nxt == now) {
return -1;
}
++answer;
now = nxt;
}
return answer;
};
const auto table = make_table();
return calc_answer(table);
}
/*
int main() {
int N, M, K;
assert(3 == scanf("%d %d %d", &N, &M, &K));
std::vector<int> C(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &C[i]));
}
std::vector<int> A(M);
std::vector<std::vector<int>> B(M);
for (int i = 0; i < M; ++i) {
assert(1 == scanf("%d", &A[i]));
B[i].resize(A[i]);
for (int j = 0; j < A[i]; ++j) {
assert(1 == scanf("%d", &B[i][j]));
}
}
int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
printf("%d\n", minimum_instructions);
}
*/
