409858: GYM103811 B Boat Assignment

In the world of Animal Crossing, Timmy and $$$N-1$$$ other animals are waiting to cross the river. Unfortunately, the bridge is destroyed by a typhoon accidentally and therefore they have to reach another side of the river by boats.

There are $$$M$$$ boats on this side of the river. The maximum load of the $$$i$$$-th boat is $$$X_i$$$ kg. Timmy weighs $$$A_1$$$ kg and the $$$i$$$-th of the other $$$N-1$$$ animals weighs $$$A_{i + 1}$$$ kg. Each boat can carry any number of animals that their total weight does not exceed the maximum load $$$X_i$$$. Also, boats cannot be combined to increase the maximum load.

Being a best friend of Timmy, you are asked to assign the animals to the boats optimally. Please tell Timmy the minimum number of boats needed for all animals to cross the river, or it is impossible under the given conditions.

The first line contains two integers $$$1 \leq N \leq 20$$$ and $$$1 \leq M \leq 50$$$.

The second line contains $$$N$$$ integers $$$A_i$$$, representing the weight of the animals. ($$$1 \leq A_i \leq 10^8$$$)

The third line contains $$$M$$$ integers $$$X_i$$$, representing the maximum load of each boat. ($$$1 \leq X_i \leq 10^9$$$)

One integer, the minimum number of boats needed for all the animals to cross the river. Or -1, if it is impossible under the given condition.

3 3
7 3 9
5 10 9

2

1 2
10
5 5

-1

In the first sample, we can assign the first and second animal to boat 2 and assign the third animal to boat 3.