题目描述

题目译自 PA 2014 Runda 2 Pakowanie

露营的时间到了！露营需要携带各种物品，并且要随身背负，因此决定哪些物品对有效露营真正必不可少非常重要。幸运的是，这不是你的任务，因为需要打包的物品已经选好了。现在剩下的只是将它们装进背包中。

每个背包可以装任意数量的物品，只要它们的总重量不超过背包的承重能力。物品不能分割，因此可能会出现背包容量未被完全利用的情况。

问题在于，背包还未购买，需要去商店选购。商店中有不同型号的背包，每个背包都有固定的承重能力，但所有背包的价格相同。你的任务是购买足够装下所有露营物品的背包，同时尽可能少花钱。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n \leq 24, 1 \leq m \leq 100)$，分别表示需要打包的物品数量和可用背包数量。

第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$ $(1 \leq a_{i} \leq 10^{8})$；数字 $a_{i}$ 表示第 $i$ 个物品的重量。

第三行包含 $m$ 个整数 $c_{1}, c_{2}, \ldots, c_{m}$ $(1 \leq c_{i} \leq 10^{8})$；数字 $c_{i}$ 表示第 $i$ 个背包的承重能力。

输出格式

输出的第一行应包含一个整数，表示足以装下所有物品的最小背包数量。如果无法装下所有物品，则应输出 NIE。

4 3
4 2 10 3
11 18 9

2