벽 칠하기

성렬이는 자기가 사는 집의 벽을 칠한지 한참 되었기 때문에 다시 칠하려고 한다. 벽은 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], …, 색 B[j][A[j] − 1] 중 하나로만 구간을 칠한다.

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

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

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

• 1 ≤ N ≤ 100000.
• 1 ≤ M ≤ min(N, 50000).
• 1 ≤ K ≤ 100000.
• 0 ≤ C[i] < K.
• 1 ≤ A[j] ≤ K.
• 0 ≤ B[j][0] < B[j][1] < … < B[j][A[j] − 1] < K.
• ∑f(k)2 ≤ 400000.