Minimum Number of Gifts

You are given a target sum \(k\) and a list of gifts. Each gift is represented by a pair of integers (id, value). The id is not used in the calculations. Your task is to select a subset of these gifts such that the sum of their values is exactly \(k\) and the number of gifts chosen is minimized.

If it is not possible to reach the sum exactly, output \(-1\). This is a typical subset sum problem with an additional optimization criterion: minimize the number of items used.

Note: Each gift can be used at most once.

inputFormat

The input is given via standard input (stdin) and has the following format:

<k>
<n>
<id1> <value1>
<id2> <value2>
...
<idn> <valuen>

Where \(k\) is the target sum, \(n\) is the number of gifts, and each subsequent line contains two integers representing the gift's id (which is ignored) and its value.

outputFormat

Output via standard output (stdout) a single integer: the minimum number of gifts needed to exactly reach the sum \(k\), or \(-1\) if it is not possible.

10
5
1 5
2 3
1 2
3 8
4 7

2