题目描述

Rie likes to make cookies. She made $N$ types of cookies. She made $A _ i$ cookies of type $i(1 \leq i \leq N)$. In order to sell the cookies made by her, she will pack them into boxes. However, the following conditions should be satisfied.

• For every box, the types of the cookies in it should be different.
• For every box, the number of cookies in it should be equal to one of the following $M$ numbers: $B _ 1, B _ 2, \cdots, B _ M$.

Write a program which, given information of cookies made by Rie and the conditions to pack the cookies into boxes, determines whether it is possible to pack all the cookies into boxes. Moreover, if it is possible to pack all the cookies into boxes, your program should output a way to pack the cookies into the minimum number of boxes.

输入格式

Read the following data from the standard input.

$N$
$A _ 1 \ A _ 2 \ \cdots \ A _ N$
$M$
$B _ 1 \ B _ 2 \ \cdots \ B _ M$

输出格式

If it is possible to pack all the cookies into boxes so that the conditions are satisfied, let $x$ be the number of used boxes, $c _ k$ be the number of cookies in the $k$-th box ($1\leq k \leq x$), and $v _ {k, 1}, v _ {k, 2}, \cdots, v _ {k, c _ k}$ be the types of the cookies in the $k$-th box. Write these numbers to the standard output as in the following format.

$x$
$c _ 1 \ v _ {1, 1} \ v _ {1, 2} \ \cdots \ v _ {1, c _ 1}$
$c _ 2 \ v _ {2, 1} \ v _ {2, 2} \ \cdots \ v _ {2, c _ 2}$
$\vdots$
$c _ x \ v _ {x, 1} \ v _ {x, 2} \ \cdots \ v _ {x, c _ x}$

Here, the number of used boxes $x$ should be the minimum possible number. If there are several ways to pack the cookies into boxes satisfying the conditions, output any one of them.

If it is impossible to pack all the cookies into boxes so that the conditions are satisfied, write $-1$ to the standard output.

题目大意

题目描述

莉婕喜欢做饼干。她制作了 $N$ 种饼干。第 $i$ 种饼干有 $A_i$ 个。为了出售她制作的饼干，她将它们装入盒子中。但是，应该满足以下条件。

• 对于每个盒子，其中的饼干种类应不同。

• 对于每个盒子，其中的饼干数量应等于以下 $M$ 个数字之一：$B_1,B_2,⋯ ,B_M$。

编写一个程序，给出莉婕制作的饼干信息和将饼干装箱的条件，确定是否可能将所有饼干包装到盒子中。此外，如果可以将所有饼干包装在盒子中，则您的程序应输出最少的盒子数量。

输入格式

从标准输入读取以下数据。

$N$
$A _ 1 \ A _ 2 \ \cdots \ A _ N$
$M$
$B _ 1 \ B _ 2 \ \cdots \ B _ M$

输出格式

如果可以将所有的饼干装入盒子并且满足上述条件，则设 $x$ 是所需的盒子数，$c_k$ 是第 $k$ 个盒子中的饼干数 $(1≤k≤x)$，$v_{k,1},v_{k,2},⋯ ,v_{k,c_k}$ 是第 $k$ 个盒子中的饼干种类。请将这些数字按以下格式编写到标准输出。

$x$
$c _ 1 \ v _ {1, 1} \ v _ {1, 2} \ \cdots \ v _ {1, c _ 1}$
$c _ 2 \ v _ {2, 1} \ v _ {2, 2} \ \cdots \ v _ {2, c _ 2}$
$\vdots$
$c _ x \ v _ {x, 1} \ v _ {x, 2} \ \cdots \ v _ {x, c _ x}$

在此，使用的盒子数量 $x$ 应该是可能的最小数量。如果有多种方式可以满足条件地将饼干装入盒子，请输出其中任何一种方法。

如果无法将所有饼干包装在盒子中以满足条件，输出 $-1$。

【样例解释 #1】

对于该样例输入，可以按照以下方式将 $7$ 个饼干装入 $3$ 个盒子中满足条件：

• 将第 $1$ 类和第 $7$ 类的饼干装入第一个盒子中。每种类型放 $1$ 个。
• 将第 $2$ 类和第 $6$ 类的饼干装入第二个盒子中。每种类型放 $1$ 个。
• 将第 $3$ 类、第 $4$ 类和第 $5$ 类的饼干装入第三个盒子中。每种类型放 $1$ 个。

因为不能用少于或等于 $2$ 个盒子来包装 $7$ 个饼干，所以以上方法是正确的。判断为正确答案。还有其他正确方法。

Translate by

7
1 1 1 1 1 1 1
3
1 2 3

3
2 1 7
2 2 6
3 3 4 5

5
5 3 1 2 4
1
4

-1

7
5 4 4 2 1 1 1
2
2 6

7
6 1 2 3 4 5 6
2 2 1
2 3 1
2 4 1
2 7 1
2 3 2
2 3 2

提示

【样例解释 #1】

In this sample input, it is possible to pack the $7$ cookies into $3$ boxes so that the conditions are satisfied as follows.

• Pack cookies of types $1, 7$ into the first box. Pack one cookie for each type.
• Pack cookies of types $2, 6$ into the second box. Pack one cookie for each type.
• Pack cookies of types $3, 4, 5$ into the third box. Pack one cookie for each type.

Your program is judged as correct if it outputs the above way to pack the cookies because it is impossible to pack the $7$ cookies into less than or equal to $2$ boxes so that the conditions are satisfied. There are other ways to pack the cookies which are judged as correct.

This sample input satisfies the constraints of Subtasks 1, 3, 4, 5, 6.

【样例解释 #2】

In this sample input, it is impossible to pack the $15$ cookies into boxes so that the conditions are satisfied.

Therefore, output $-1$.

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6.

【样例解释 #3】

This sample input satisfies the constraints of Subtasks 4, 5, 6.

【数据范围】

对于所有测试数据，满足 $1 \leq N \leq 15 000$，$A _ i \geq 1$（$1 \leq i \leq n$），$A _ 1 + A _ 2 + \cdots + A _ N \leq 15 000$，$1 \leq M \leq N$，$1 \leq B _ j \leq N$（$1 \leq j \leq M$），$B _ j < B _ {j + 1}$（$1 \leq j \leq M - 1$），保证所有输入均为整数。

子任务编号	分值	限制
$1$	$6$	$N \leq 500$，$A _ i = 1$（$1 \leq i \leq N$）
$2$	$7$	$N \leq 500$，$M = 1$
$3$	$12$	$A _ 1 + A _ 2 + \cdots + A _ N \leq 15$
$4$	$45$	$A _ 1 + A _ 2 + \cdots + A _ N \leq 500$
$5$	$15$	$A _ 1 + A _ 2 + \cdots + A _ N \leq 3000$
$6$		没有额外的限制