P5997 [PA 2014] Packing

You have $n$ items and $m$ bags. Each item has a weight and cannot be split; each bag has its own capacity. To pack all items into the bags, what is the minimum number of bags needed?

The first line contains two integers $n, m$, representing the number of items and the number of bags. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, where $a_i$ is the weight of the $i$-th item. The third line contains $m$ integers $c_1, c_2, \ldots, c_m$, where $c_i$ is the capacity of the $i$-th bag.

If it is possible to pack all items, output one integer representing the minimum number of bags used. If it is not possible to pack all items, output `NIE`.

For $100\%$ of the testdata, $1 \le n \le 24$, $1 \le m \le 100$, $1 \le a_i \le 10^8$, $1 \le c_i \le 10^8$. Translated by ChatGPT 5