← 返回题目列表

Codeforces · 1798/F

F. 祖父艾哈迈德的礼物

中文机器翻译题面 查看原题

祖父艾哈迈德的学校有 $$$n+1$$$ 名学生。学生被分为 $$$k$$$ 个班级,$$$s_i$$$ 学生在第 $$$i$$$ 班级学习。所以,$$$s_1 + s_2 + \ldots + s_k = n+1$$$。

由于愚人节即将到来,所有学生都会收到礼物!

祖父艾哈迈德计划订购 $$$n+1$$$ 盒礼物。每个盒子可以包含一件或多件礼物。他计划在班级之间分配这些盒子,以满足以下条件:

1. $$$i$$$ 班级收到恰好 $$$s_i$$$ 个盒子(这样每个学生只能打开一个盒子)。
2、第$$$i$$$班级收到的盒子里的礼物总数应该是$$$s_i$$$的倍数(应该可以将礼物平均分配给本班级的$$$s_i$$$学生)。

不幸的是,祖父艾哈迈德只订购了 $$$n$$$ 盒礼物,其中 $$$i$$$ 包含 $$$a_i$$$ 礼物。

艾哈迈德必须购买丢失的礼品盒,并且礼品盒中的礼品数量应为 $$$1$$$ 到 $$$10^6$$$ 之间的整数。帮助艾哈迈德确定丢失的盒子应该包含多少礼物,并为班级制定合适的盒子分配方案,或者报告这是不可能的。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 200$$$, $$$k \le n + 1$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — 可用盒子中的礼物数量。

第三行包含 $$$k$$$ 整数 $$$s_1, s_2, \ldots, s_k$$$ ($$$1 \le s_i \le n+1$$$) — 班级中的学生人数。保证 $$$\sum s_i = n+1$$$。

输出

如果没有办法购买剩余的盒子,则单行输出整数$$$-1$$$。

否则,在第一行中,输出一个整数 $$$s$$$ — 祖父艾哈迈德应该购买的盒子里的礼物数量 ($$$1 \le s \le 10^6$$$)。

接下来,在 $$$k$$$ 行中,打印框到类的分布。在第 $$$i$$$ 行中打印 $$$s_i$$$ 整数 — 应发送到第 $$$i$$$ 类的盒子的大小。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

4 2
7 7 7 127
2 3

输出 #1

1
7 7 
7 127 1

输入 #2

18 4
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
6 1 9 3

输出 #2

9
7 1 7 6 5 4 
9 
1 2 3 8 3 2 9 8 9 
6 5 4

注意

在第一个测试中,祖父艾哈迈德只需 $$$1$$$ 礼物即可购买一盒。之后,两盒装有$$$7$$$礼物的礼物被送到头等舱。 $$$7 + 7 = 14$$$ 可以被 $$$2$$$ 整除。第二类获得装有 $$$1、7、127$$$ 礼物的盒子。 $$$1 + 7 + 127 = 135$$$ 可以被 $$$3$$$ 整除。

在第二个测试中,类的大小为 $$$6$$$、$$$1$$$、$$$9$$$ 和 $$$3$$$。我们表明,可用的盒子足以分配到尺寸为 $$$6$$$、$$$9$$$、$$$3$$$ 的类中,并且在尺寸为 $$$1$$$ 的类中,您可以购买任何尺寸的盒子。在尺寸为 $$$6$$$ 的班级中,我们发送尺寸为 $$$7$$$、$$$1$$$、$$$7$$$、$$$6$$$、$$$5$$$、$$$4$$$ 的盒子。 $$$7 + 1 + 7 + 6 + 5 + 4 = 30$$$ 可以被 $$$6$$$ 整除。在尺寸为 $$$9$$$ 的班级中,我们发送尺寸为 $$$1$$$、$$$2$$$、$$$3$$$、$$$8$$$、$$$3$$$、$$$2$$$、$$$9$$$、$$$8$$$、$$$9$$$ 的盒子。 $$$1 + 2 + 3 + 8 + 3 + 2 + 9 + 8 + 9 = 45$$$ 可以被 $$$9$$$ 整除。剩余的盒子($$$6$$$、$$$5$$$、$$$4$$$)被发送到大小为 $$$3$$$ 的班级。 $$$6 + 5 + 4 = 15$$$ 可以被 $$$3$$$ 整除。