벽 칠하기 Batch 컴파일 명령

설명 

성렬이는 자기가 사는 집의 벽을 칠한지 한참 되었기 때문에 다시 칠하려고 한다. 벽은 $N$개의 구간으로 되어 있는데, $0$부터 $N - 1$까지 번호가 매겨져 있다. 이 문제에서, $K$ 가지 다른 색깔이 있고 이 색을 각각 $0$ 이상 $K - 1$ 이하인 정수로 표현하자 (예를 들면, 붉은 색은 $0$, 파란 색은 $1$, 등등 같은 식으로) 성렬이는 벽의 $i$ 번째 구간을 색깔 $C[i]$로 칠하려고 한다.

성렬이는 벽 칠해주는 회사에 이 일을 맡기기로 했는데, 이 회사에는 $M$ 명의 일꾼이 있고 각 일꾼은 $0$ 부터 $M - 1$ 까지 번호가 매겨져 있다. 불행히도, 일꾼들은 자기가 좋아하는 색만 칠하려고 한다. 구체적으로는, $j$ 번 일꾼은 $A[j]$ 개의 색을 좋아하고, 색 $B[j][0]$, 색 $B[j][1]$, $\ldots$, 색 $B[j][A[j] - 1]$ 중 하나로만 구간을 칠한다.

성렬이는 벽 칠해주는 회사에 여러 번 지령을 보낼 수 있다. 성렬이가 회사에 보내는 지령 하나는 두 파라미터  $x$와 $y$로 이루어지는데, $0 \le x \lt M$이고 $0 \le y \le N - M$이다. 모든 $0 \le l \lt M$에 대해서 회사는  ($(x + l) \bmod M$)번 일꾼 에게 ($y + l$) 번째 구간을 칠하게 시킨다. 만약 어떤 $l$ 값에서 ($(x + l) \bmod M$)번 일꾼이 색 $C[y + l]$을 좋아하지 않는 경우가 있다면, 이 지령은 무효가 된다.  

성렬이는 지령 하나를 보낼 때마다 돈을 내야 하기 때문에, 가능하다면 벽의 모든 구간을 원하는 색깔로 칠하는 명령의 최소 횟수, 또는 원하는 색깔로 벽을 칠할 수 없다는 것을 알고 싶다. 동일한 구간을 여러번 칠할 수 있지만, 항상 원하는 색깔로 칠해야 한다.  

할 일 

다음 minimumInstructions 함수를 구현해야 한다.  

• minimumInstructions(N, M, K, C, A, B) - 이 함수는 그레이더에 의해 정확하게 한 번 호출된다.
  • $N$: 구간의 수를 나타내는 정수.
  • $M$: 일꾼의 수를 나타내는 정수.  
  • $K$: 색의 수를 나타내는 정수.  
  • $C$: 길이 $N$인 정수 배열로 각 구간마다 원하는 색깔을 나타낸다.  
  • $A$: 길이 $M$인 정수 배열로 각 일꾼이 좋아하는 색의 수을 나타낸다.  
  • $B$: 길이 $M$인 정수 배열들의 배열로 각 일꾼이 좋아하는 색을 나타낸다.  
  • 이 함수의 리턴 값은 성렬이가 모든 구간을 원하는 색으로 칠하기 위해 필요한 지령의 최소 개수이다. 만약 이렇게 칠하는 것이 불가능하다면 $-1$을 리턴한다.  

예제 

첫번째 예제에서, $N = 8$, $M = 3$, $K = 5$, $C = [3, 3, 1, 3, 4, 4, 2, 2]$, $A = [3, 2, 2]$, $B = [[0, 1, 2], [2, 3], [3, 4]]$이다. 성렬이는 다음과 같은 지령을 내릴 수 있다.  

1. $x = 1$, $y = 0$. 1번 일꾼이 0번 구간을 칠할 수 있고, 2번 일꾼이 1번 구간을 칠할 수 있고, 0번 일꾼이 2번 구간을 칠할 수 있으므로 이 지령은 타당하다.  
2. $x = 0$, $y = 2$. 0번 일꾼이 2번 구간을 칠할 수 있고, 1번 일꾼이 3번 구간을 칠할 수 있고, 2번 일꾼이 4번 구간을 칠할 수 있으므로 이 지령은 타당하다.  
3. $x = 2$, $y = 5$. 2번 일꾼이 5번 구간을 칠할 수 있고, 0번 일꾼이 6번 구간을 칠할 수 있고, 1번 일꾼이 7번 구간을 칠할 수 있으므로 이 지령은 타당하다.  

성렬이가 $3$개보다 적은 지령으로 모든 구간을 원하는 색깔로 칠할 수 없다는 것을 쉽게 보일 수 있기 때문에,   minimumInstructions(8, 3, 5, [3, 3, 1, 3, 4, 4, 2, 2], [3, 2, 2], [[0, 1, 2], [2, 3], [3, 4]])의 리턴값은 $3$이어야 한다.

두번째 예제에서, $N = 5$, $M = 4$, $K = 4$, $C = [1, 0, 1, 2, 2]$, $A = [2, 1, 1, 1]$, $B = [[0, 1], [1], [2], [3]]$이다. 3번 일꾼은 색 $3$만 좋아하는데 색 $3$으로 칠할 구간이 없기 때문에, 성렬이가 어떤 지령을 내리더라도 무효가 된다. 따라서, minimumInstructions(5, 4, 4, [1, 0, 1, 2, 2], [2, 1, 1, 1], [[0, 1], [1], [2], [3]])의 리턴값은 $-1$이어야 한다.

제약조건

$0 \le k \lt K$에 대해서, $f(k)$가 $j$번 일꾼이 색 $k$를 좋아하는 $j$의 개수라고 하자. (즉, 색 $k$를 좋아하는 일꾼의 수이다.) 예를 들어, 만약 $f(1) = 2$이라면, 색 $1$을 좋아하는 일꾼이 둘 있다.

• $1 \le N \le 100\,000$.
• $1 \le M \le \min(N, 50\,000)$.
• $1 \le K \le 100\,000$.
• $0 \le C[i] \lt K$.
• $1 \le A[j] \le K$.
• $0 \le B[j][0] \lt B[j][1] \lt \ldots \lt B[j][A[j] - 1] \lt K$.
• $ \sum f(k)^2 \le 400\,000$.

Subtask 1 (12 points)

• $f(k) \le 1$.

Subtask 2 (15 points)

• $N \le 500$.
• $M \le \min(N, 200)$.
• $ \sum f(k)^2 \le 1\,000$.

Subtask 3 (13 points)

• $N \le 500$.
• $M \le \min(N, 200)$.

Subtask 4 (23 points)

• $N \le 20\,000$.
• $M \le \min(N, 2\,000)$.

Subtask 5 (37 points)

• 추가적인 제약 조건이 없다. 

샘플 그레이더

샘플 그레이더는 입력을 다음 양식으로 읽는다.  

N M K
C[0] C[1] ... C[N-1]
A[0] B[0][0] B[0][1] ... B[0][A[0]-1]
A[1] B[1][0] B[1][1] ... B[1][A[1]-1]
.
.
.
A[M-1] B[M-1][0] B[M-1][1] ... B[M-1][A[M-1]-1]

샘플 그레이더는 minimumInstructions 함수의 리턴값을 출력한다.  

첨부

공개된 그레이더, 예제 케이스, 문제에 대한 기본 파일은 `paint.zip`에 첨부되어 있다.