It is time for a camping trip! You need to take various things with you, and then carry them, so deciding which items are truly essential for effective camping is very important. Fortunately, that is not your task, as the items to be packed have already been selected. Now, all that remains is to pack them into backpacks.

You can put any number of items into each backpack, as long as their total mass does not exceed its capacity. Items cannot be divided, so it may turn out that the capacity of the used backpacks will not be fully utilized.

The problem is that you do not have any backpacks yet and need to buy them. Various models of backpacks are available in the store. Each backpack is characterized by a fixed capacity, and the price of all backpacks is the same. Your task is to buy backpacks that are sufficient to pack all the items for the camping trip while spending as little as possible.

Input

The first line of input contains two integers $n$ and $m$ ($1 \le n \le 24$, $1 \le m \le 100$), specifying the number of items to pack and the number of available backpacks. The second line contains a sequence of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^8$); the number $a_i$ specifies the mass of the $i$-th item. The third line contains a sequence of $m$ integers $c_1, c_2, \dots, c_m$ ($1 \le c_i \le 10^8$); the number $c_i$ specifies the capacity of the $i$-th backpack.

Output

The first line of output should contain a single integer representing the minimum number of backpacks sufficient to pack all the items. If it is not possible to pack the items, you should output the word NIE instead.

Examples

Input 1

4 3
4 2 10 3
11 18 9

Output 1

2

Note

For the example, you can, for instance, purchase the first and third backpacks. The heaviest item can then be placed in the backpack with a capacity of 11, while the remaining items can be placed in the backpack with a capacity of 9.