캐시

어떤 시스템이 크기가 서로 다른 물체 $N$개를 사용한다. 시스템은 캐시에 들어 있는 물체만 사용할 수 있다. 요청한 물체가 캐시에 없으면 먼저 캐시에 넣어야 하고, 자리가 부족하면 그 전에 다른 물체를 지워서 공간을 확보한다. 캐시의 남은 공간을 모두 합쳐 $S_i$ 이상이면 크기가 $S_i$인 물체를 넣을 수 있다. 물체 $i$를 캐시에 넣는 비용은 $W_i$이고, 캐시에서 지우는 비용은 0이다. 캐시에는 크기의 합이 $C$ 이하인 물체 집합만 들어간다. 처음에 캐시는 비어 있고, 물체는 요청된 순간에만 캐시에 넣을 수 있다. 시스템이 물체를 사용하는 순서는 미리 알고 있다. 캐시에 물체를 넣는 비용의 합이 최소가 되도록 어떤 물체를 언제 지울지 정하라.

첫째 줄에 정수 $N$, $C$, $K$가 주어진다 ($1 \le N \le 18$, $1 \le C \le 10^9$, $1 \le K \le 100$). $K$는 요청의 개수다.

둘째 줄에 물체의 크기 $S_1, S_2, \dots, S_N$이 주어진다 ($1 \le S_i \le C$).

셋째 줄에 물체를 캐시에 넣는 비용 $W_1, W_2, \dots, W_N$이 주어진다 ($0 \le W_i \le 10^6$).

넷째 줄에 시스템이 사용하는 순서대로 물체 번호 $K$개가 주어진다. 각 번호는 1 이상 $N$ 이하다. 한 줄에 있는 수는 공백으로 구분한다.

첫째 줄에 캐시에 물체를 넣는 비용의 합의 최솟값을 출력한다. 이어서 $K$개의 줄을 출력한다. $i$번째 줄에는 $i$번째로 요청된 물체를 사용하기 직전에 캐시에서 지우는 물체를 적는다. 줄의 첫 수는 지우는 물체의 개수 $m$이고, 그 뒤에 물체 번호 $m$개를 쓴다. 한 줄에 있는 수는 공백으로 구분한다.

최소 비용을 달성하는 삭제 계획이 여러 개일 수 있으므로 다음 규칙으로 하나를 고른다. 각 줄의 물체 번호는 증가하는 순서로 적는다. 첫째 줄을 뺀 나머지 출력을 위에서 아래로 이어 읽어 하나의 수열로 볼 때, 비용이 최소인 계획 중 이 수열이 사전순으로 가장 앞서는 것을 출력한다. 각 줄의 첫 수가 지우는 개수이므로, 요청한 물체가 이미 캐시에 있거나 남은 공간에 그대로 들어가면 이 계획은 아무것도 지우지 않는다.