{"problem":{"name":"[JOIST 2023] 曲奇 / Cookies","description":{"content":"莉婕喜欢做饼干。她制作了 $N$ 种饼干。第 $i$ 种饼干有 $A_i$ 个。为了出售她制作的饼干，她将它们装入盒子中。但是，应该满足以下条件。 + 对于每个盒子，其中的饼干种类应不同。 + 对于每个盒子，其中的饼干数量应等于以下 $M$ 个数字之一：$B_1,B_2,⋯ ,B_M$。 编写一个程序，给出莉婕制作的饼干信息和将饼干装箱的条件，确定是否可能将所有饼干包装到盒子中。此外，如果可","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9339"},"statements":[{"statement_type":"Markdown","content":"莉婕喜欢做饼干。她制作了 $N$ 种饼干。第 $i$ 种饼干有 $A_i$ 个。为了出售她制作的饼干，她将它们装入盒子中。但是，应该满足以下条件。\n\n+ 对于每个盒子，其中的饼干种类应不同。\n\n+ 对于每个盒子，其中的饼干数量应等于以下 $M$ 个数字之一：$B_1,B_2,⋯ ,B_M$。\n\n编写一个程序，给出莉婕制作的饼干信息和将饼干装箱的条件，确定是否可能将所有饼干包装到盒子中。此外，如果可以将所有饼干包装在盒子中，则您的程序应输出最少的盒子数量。\n\n## Input\n\n从标准输入读取以下数据。\n> $N$  \n> $A _ 1 \\ A _ 2 \\ \\cdots \\ A _ N$  \n> $M$  \n> $B _ 1 \\ B _ 2 \\ \\cdots \\ B _ M$\n\n## Output\n\n如果可以将所有的饼干装入盒子并且满足上述条件，则设 $x$ 是所需的盒子数，$c_k$ 是第 $k$ 个盒子中的饼干数 $(1≤k≤x)$，$v_{k,1},v_{k,2},⋯ ,v_{k,c_k}$ 是第 $k$ 个盒子中的饼干种类。请将这些数字按以下格式编写到标准输出。\n> $x$  \n> $c _ 1 \\ v _ {1, 1} \\ v _ {1, 2} \\ \\cdots \\ v _ {1, c _ 1}$  \n> $c _ 2 \\ v _ {2, 1} \\ v _ {2, 2} \\ \\cdots \\ v _ {2, c _ 2}$  \n> $\\vdots$  \n> $c _ x \\ v _ {x, 1} \\ v _ {x, 2} \\ \\cdots \\ v _ {x, c _ x}$ \n\n在此，使用的盒子数量 $x$ 应该是可能的最小数量。如果有多种方式可以满足条件地将饼干装入盒子，请输出其中任何一种方法。\n\n如果无法将所有饼干包装在盒子中以满足条件，输出 $-1$。\n\n[samples]\n\n## Note\n\n#### 【样例解释 #1】\n\n对于该样例输入，可以按照以下方式将 $7$ 个饼干装入 $3$ 个盒子中满足条件：\n\n+ 将第 $1$ 类和第 $7$ 类的饼干装入第一个盒子中。每种类型放 $1$ 个。\n+ 将第 $2$ 类和第 $6$ 类的饼干装入第二个盒子中。每种类型放 $1$ 个。\n+ 将第 $3$ 类、第 $4$ 类和第 $5$ 类的饼干装入第三个盒子中。每种类型放 $1$ 个。\n\n因为不能用少于或等于 $2$ 个盒子来包装 $7$ 个饼干，所以以上方法是正确的。判断为正确答案。还有其他正确方法。\n\n**【数据范围】**\n\n对于所有测试数据，满足 $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$），保证所有输入均为整数。\n\n| **子任务编号** | **分值** | **限制** |\n| :----------: | :----------: | :----------: |\n| $1$ | $6$ | $N \\leq 500$，$A _ i = 1$（$1 \\leq i \\leq N$） |\n| $2$ | $7$ | $N \\leq 500$，$M = 1$ |\n| $3$ | $12$ | $A _ 1 + A _ 2 + \\cdots + A _ N \\leq 15$ |\n| $4$ | $45$ | $A _ 1 + A _ 2 + \\cdots + A _ N \\leq 500$ |\n| $5$ | $15$ | $A _ 1 + A _ 2 + \\cdots + A _ N \\leq 3000$ |\n| $6$ | $15$ | 没有额外的限制 |\n\nTranslate by @[ZeXic_B](https://www.luogu.com.cn/user/661274)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9339","tags":["2023","Special Judge","O2优化","背包 DP","二分图","bitset","JOISC/JOIST（日本）"],"sample_group":[["7\n1 1 1 1 1 1 1\n3\n1 2 3","3\n2 1 7\n2 2 6\n3 3 4 5"],["5\n5 3 1 2 4\n1\n4","-1"],["7\n5 4 4 2 1 1 1\n2\n2 6","7\n6 1 2 3 4 5 6\n2 2 1\n2 3 1\n2 4 1\n2 7 1\n2 3 2\n2 3 2"]],"created_at":"2026-03-03 11:09:25"}}