Cache

A system uses $N$ objects of different sizes. The system can use an object only while the object is in the cache. If a requested object is not in the cache, it must be put there first, and other objects may be deleted beforehand to free enough room. An object of size $S_i$ fits as soon as the total free space in the cache is at least $S_i$. Putting object $i$ into the cache costs $W_i$, and deleting an object from the cache costs 0. The cache holds any set of objects whose total size is at most $C$. The cache is empty at the start, and an object may be put into the cache only at the moment it is requested. You know the order in which the system uses the objects. Decide which objects to delete and when to delete them so that the total cost of putting objects into the cache is as small as possible.

The first line contains three integers $N$, $C$ and $K$ ($1 \le N \le 18$, $1 \le C \le 10^9$, $1 \le K \le 100$), where $K$ is the number of requests.

The second line contains $N$ integers $S_1, S_2, \dots, S_N$, the sizes of the objects ($1 \le S_i \le C$).

The third line contains $N$ integers $W_1, W_2, \dots, W_N$, the cost of putting each object into the cache ($0 \le W_i \le 10^6$).

The fourth line contains $K$ object numbers in the order the system uses them. Each number is between 1 and $N$. Numbers on one line are separated by spaces.

Print the minimum total cost of putting objects into the cache on the first line. Then print $K$ lines. Line $i$ lists the objects deleted from the cache right before the $i$-th requested object is used. The first number on the line is the count $m$ of deleted objects, followed by the $m$ object numbers. Numbers on one line are separated by spaces.

Several deletion plans can reach the minimum cost, so print the one picked by these rules. Write the object numbers on each line in increasing order. Read everything after the first line as a single sequence of numbers, taken line by line, and among the plans of minimum total cost print the one whose sequence comes first in lexicographic order. Because the first number on each line is the count, this plan deletes nothing when the requested object is already in the cache or still fits in the free space.