Minimum Bags Required

You are given n items and m bags. Each item has a weight and cannot be divided, and each bag has its own capacity. Your task is to determine the minimum number of bags required to pack all items so that the total weight of the items placed in a bag does not exceed its capacity.

This can be mathematically formulated as follows:

Let the items have weights \(w_1, w_2, \dots, w_n\), and the bags have capacities \(c_1, c_2, \dots, c_m\). Find the smallest integer \(k\) (with \(1\le k\le m\)) for which it is possible to select \(k\) bags and assign each item to one bag such that for every selected bag \(j\), the sum of weights assigned to that bag is at most \(c_j\). If it is impossible to pack all items, output -1.

inputFormat

The input consists of three lines.

• The first line contains two integers \(n\) and \(m\) representing the number of items and bags respectively.
• The second line contains \(n\) integers: the weights of the items.
• The third line contains \(m\) integers: the capacities of the bags.

outputFormat

Output a single integer representing the minimum number of bags required to pack all items. If it is impossible to pack all items, output -1.

sample

3 4
2 4 3
5 3 4 3

2