Codeforces Round 860 (Div. 2) |
---|
Закончено |
В Школе Деда Ахмеда обучается $$$n+1$$$ ученик. Ученики разбиты на $$$k$$$ классов, и в $$$i$$$-м классе обучается $$$s_i$$$ учеников. Таким образом, $$$s_1 + s_2 + \ldots + s_k = n+1$$$.
В честь скорого Дня дурака все ученики получат подарки!
Дед Ахмед планировал заказать $$$n+1$$$ коробку с подарками. В каждой коробке будет один или несколько подарков. Дед Ахмед распределит их между классами так, чтобы были выполнены следующие условия:
К сожалению, Дед Ахмед по невнимательности заказал всего $$$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$$$-й класс.
Если существует несколько решений, выведите любое из них.
4 2 7 7 7 127 2 3
1 7 7 7 127 1
18 4 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 6 1 9 3
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$$$. В класс размера $$$3$$$ отправятся оставшиеся коробки размеров $$$6$$$, $$$5$$$, $$$4$$$. $$$6 + 5 + 4 = 15$$$ нацело делится на $$$3$$$.
Название |
---|