B. Boat Assignment
time limit per test
1 s
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$)

Output

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.

Examples
Input
3 3
7 3 9
5 10 9
Output
2
Input
1 2
10
5 5
Output
-1
Note

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