31325번 - Devil's Hell deLivery 스페셜 저지다국어

문제

Devil's Hell deLivery company delivers literally everything: boxes, packages, packets, datagrams et cetera.

The delivery process from city A to city B works as follows. There are $N$ trucks and $K$ items. The capacity of truck number $i$ equals $c_i$. The weight of item number $j$ equals $w_j$. The trucks make one or more delivery steps.

During one step, some items are loaded into some trucks. Items can not be split. Each truck's capacity must not be exceeded by the total weight of the items assigned to it. All trucks depart simultaneously.

At the end of each step, all trucks come back to the place where they started. If there are any items left, another step is performed.

Your task is to distribute items among steps and trucks so that the number of steps is minimized.

입력

The input contains up to a hundred test cases.

Each test case starts with a single line containing two integers $N$ and $K$ (1ドル \le N \le 5,ドル 1ドル \le K \le 9$): the number of trucks and the number of items, respectively. The following line consists of $N$ integers $c_1, \ldots, c_N$ (1ドル \le c_i \le 10^8$): the capacities of the trucks. The following line consists of $K$ integers $w_1, \ldots, w_K$ (1ドル \le w_i \le 10^8$): the weights of the items.

출력

For each test case, if the delivery is impossible, write a single line with a single integer $-1$.

Otherwise, start with a line containing a single integer $S$: the number of steps required. This number must be minimized. After that, write $S$ lines describing the steps. Each step description must start with an integer $I_i,ドル the number of items delivered during the step. This number must be followed by $I_i$ pairs $a_j$ $b_j$. Each pair $a_j$ $b_j$ means that the item $a_j$ is assigned to the truck $b_j$.

If there is more than one possible optimal answer, write any one of them.

제한

힌트