#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
const int INF = 1000000010;
int m;
int dp[MAXN];
vector<int> dpComp[MAXN];
vector<int> company[MAXN];
multiset<int> minDP;
bool isGood(int i)
{
for(int j = 0 ; j < (int)dpComp[i].size() ; j++)
if( dpComp[i][j] >= m ) return true;
return false;
}
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector< vector<int> > B)
{
m = M;
C.push_back( K + 1 );
for(int i = 0 ; i < M ; i++)
for(int j = 0 ; j < A[i] ; j++)
company[ B[i][j] ].push_back( i );
for(int i = N - 1 ; i >= 0 ; i--)
{
dpComp[i].resize( company[ C[i] ].size() , 0 );
int pB = 0;
int maxB = (int)company[ C[i + 1] ].size();
for(int pA = 0 ; pA < (int)company[ C[i] ].size() ; pA++)
{
while( pB < maxB )
{
int nxt = company[ C[i + 1] ][pB];
if( company[ C[i] ][pA] < nxt ) break;
pB++;
}
if( pB < maxB && company[ C[i] ][pA] == company[ C[i + 1] ][pB] - 1 )
dpComp[i][pA] = dpComp[i + 1][pB];
}
if( !company[ C[i] ].empty() && !company[ C[i + 1] ].empty() )
{
int ind = (int)company[ C[i] ].size() - 1;
if( company[ C[i] ].back() == M - 1 && company[ C[i + 1] ].front() == 0 )
dpComp[i][ind] = dpComp[i + 1][0];
}
for(int j = 0 ; j < (int)dpComp[i].size() ; j++)
dpComp[i][j]++;
}
dp[N] = 0;
for(int i = 0 ; i < N ; i++)
dp[i] = INF;
for(int i = N - M + 1 ; i <= N ; i++)
minDP.insert( dp[i] );
for(int i = N - M ; i >= 0 ; i--)
{
if( isGood( i ) )
dp[i] = *minDP.begin() + 1;
minDP.insert( dp[i] );
minDP.erase( minDP.find( dp[i + M] ) );
}
if( dp[0] >= INF ) return -1;
return dp[0];
}
