理惠女士喜欢做曲奇。她做了 $N$ 种曲奇,第 $i\ (1\le i\le N)$ 种做了 $A_i$ 个。为了卖这些曲奇,她会将曲奇打包进盒子中。然而,需要满足以下条件:
- 对于每个盒子,在其中的曲奇种类应该是不同的
- 对于每个盒子,在其中的曲奇数应该等于如下 $M$ 个数中的一个:$B_1,B_2,\ldots,B_M$
给定理惠女士做的曲奇的信息和打包的要求,写一个程序确定是否可以把所有曲奇打包。此外,如果可以将所有曲奇打包,你的程序应该输出一种使用最少的盒子的打包方案。
输入格式
第一行一个整数 $N$。
第二行 $N$ 个整数 $A_1,A_2,\ldots,A_N$。
第三行一个整数 $M$。
第四行 $M$ 个整数 $B_1,B_2,\ldots,B_M$。
输出格式
如果可以将所有曲奇打包并满足条件,第一行输出最少的盒子使用数 $x$。接下来输出 $x$ 行表示打包方案。第 $k\ (1\le k\le x)$ 行先输出一个整数 $c_k$,表示第 $k$ 个盒子中的曲奇数,接下来在这行输出 $c_k$ 个整数 $v_{k,1},v_{k,2},\ldots,v_{k,c_k}$,表示放在这个盒子中的曲奇种类。如果在满足使用盒子数最少的情况下,有多种打包方案满足条件,输出任意一种均可。
如果不可能将所有曲奇打包,输出一行一个整数 $-1$ 即可。
样例输入 1
7 1 1 1 1 1 1 1 3 1 2 3
样例输出 1
3 2 1 7 2 2 6 3 3 4 5
在这组样例中,可以按如下方式将 $7$ 块曲奇打包进 $3$ 个盒子中,并满足条件:
- 将第 $1,7$ 种曲奇放进第一个盒子中,每种曲奇放一个
- 将第 $2.6$ 种曲奇放进第二个盒子中,每种曲奇放一个
- 将第 $3,4,5$ 种曲奇放进第三个盒子中,每种曲奇放一个
如果你的程序按如上方式输出将被判为正确,因为不可能将这 $7$ 块曲奇放进 $2$ 个或更少的盒子中并满足条件。如果有其他打包曲奇的正确方式也会被判为正确。
这组样例满足子任务 $1,3,4,5,6$ 的限制。
样例输入 2
5 5 3 1 2 4 1 4
样例输出 2
-1
在这组样例中,不可能将 $15$ 块曲奇打包进盒子中并满足条件。因此输出 $-1$。
这组样例满足子任务 $2,3,4,5,6$ 的限制。
样例输入 3
7 5 4 4 2 1 1 1 2 2 6
样例输出 3
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
这组样例满足子任务 $4,5,6$ 的限制。
数据范围
对于所有输入数据,满足:
- $1\le N\le 15\ 000$
- $A_i\ge 1,A_1+A_2+\ldots+A_N\le 15\ 000$
- $1\le M\le N$
- $1\le B_j\le N,B_j < B_{j+1}$
详细子任务附加限制及分值如下表所示。
子任务编号 | 附加限制 | 分值 |
---|---|---|
$1$ | $N\le 500,A_i=1$ | $6$ |
$2$ | $N\le 500,M=1$ | $7$ |
$3$ | $A_1+A_2+\ldots+A_N\le 15$ | $12$ |
$4$ | $A_1+A_2+\ldots+A_N\le 500$ | $45$ |
$5$ | $A_1+A_2+\ldots+A_N\le 3\ 000$ | $15$ |
$6$ | 无附加限制 | $15$ |
时间限制:1s
空间限制:1024 MB