메모리 관리자

Peter는 특수한 자기 7D 블록을 사용하는 오프라인 저장 장치를 위한 메모리 관리자 MEM 2.0을 개발하고 있다. 그런데 데이터를 최적으로 접근하는 방법에 문제가 있다.

Peter의 메모리 관리자는 n개의 데이터 블록을 저장하며, 블록은 1번부터 n번까지 번호가 매겨져 있다. 그리고 하나 또는 여러 블록에 접근하는 q개의 쿼리가 있다. 쿼리는 나열된 순서대로 처리해야 한다.

데이터에 접근하기 위해 Peter의 메모리 관리자에는 k개의 포인터가 있고, 각 포인터는 어떤 블록을 가리킨다. 처음에 Peter는 포인터를 원하는 블록에 배치할 수 있다.

MEM 2.0은 요청된 블록 각각에 현재 포인터가 하나씩 있다면 그 블록들의 데이터에 즉시 접근한다. 그렇지 않으면 먼저 포인터를 움직여야 하며, 이 연산은 i번째 쿼리에 대해 포인터를 몇 개 움직이든 총 si밀리초가 걸린다.

Peter는 모든 쿼리에 답하는 데 걸리는 총 시간이 최소가 되도록 포인터를 움직이려고 한다. 쿼리는 나열된 순서대로 처리해야 하고, 순서를 바꿀 수 없다. 그를 도와주자.

예제를 살펴보자.

첫 번째 예제에서 Peter는 처음에 포인터를 블록 1, 2, 4에 배치할 수 있다. 그러면 처음 두 쿼리는 즉시 접근된다. 세 번째 쿼리 전에 포인터를 블록 2, 3, 5로 움직여야 하고 s3 = 1밀리초가 걸리며, 네 번째 쿼리 전에 포인터를 블록 1, 3, 5로 움직이는 데 s4 = 1밀리초가 더 걸린다. 총 시간은 s3 + s4 = 2밀리초이다.

두 번째 예제는 탐욕적인 선택이 항상 최적인 것은 아님을 보여준다. 처음에 포인터를 1, 2, 4에 배치하여 처음 두 쿼리를 즉시 처리하지 않는 편이 낫다. 그러면 세 번째 쿼리 전에 포인터를 움직이는 데 10밀리초가 걸리기 때문이다. 최적의 전략은 처음에 포인터를 블록 1, 2, 3에 배치하고, 두 번째 쿼리 전에 s2 = 1밀리초에 블록 1, 3, 4로 움직이고, 네 번째 쿼리 전에 s4 = 3밀리초에 블록 1, 3, 5로 움직이는 것이다. 총 시간은 s2 + s4 = 4밀리초이다.

입력 데이터는 여러 테스트 케이스를 포함한다. 첫째 줄에는 테스트 케이스의 수 t가 주어진다 (1 ≤ t ≤ 1000).

다음 t개의 테스트 케이스는 각각 다음과 같이 주어진다. 첫째 줄에는 세 정수 n, k, q가 주어진다. n은 블록의 수, k는 포인터의 수, q는 쿼리의 수이다 (1 ≤ k ≤ n ≤ 105, 1 ≤ q ≤ 106).

다음 줄에는 q개의 정수 si가 주어진다. si는 i번째 쿼리 전에 포인터를 움직일 때 걸리는 시간이다 (1 ≤ si ≤ 104).

다음 q개의 줄에는 처리해야 하는 순서대로 쿼리가 주어진다. i번째 쿼리는 먼저 요청하는 블록의 수 ci (1 ≤ ci ≤ k)가 주어지고, 이어서 ci개의 정수 bi, j가 오름차순으로 주어진다 (1 ≤ bi, j ≤ n).

하나의 입력 데이터에서 모든 n의 합은 105를 넘지 않고, 한 입력 데이터의 모든 테스트 케이스에서 모든 ci의 합은 106을 넘지 않는다.

각 테스트 케이스마다 모든 쿼리에 답하는 데 필요한 최소 총 시간을 한 줄에 하나씩 출력한다.