Vending Machine Snack Selection

You are given a vending machine that works in a unique way. The machine dispenses snacks in order to maximize the number of distinct snack types purchased with a limited amount of money. The machine always selects snacks in increasing order of their cost until there is no money left to buy the next affordable snack.

Formally, let \( M \) represent the available money and let there be \( n \) snacks described by their name and cost. The machine sorts the snacks by their cost in ascending order. Then, starting from the cheapest snack, the machine subtracts the snack cost from \( M \) and dispenses that snack if \( M \geq \) cost. This process continues until no further snack can be afforded.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains a single integer \( M \) which denotes the available money.
2. The second line contains a single integer \( n \) indicating the number of snack types.
3. The next \( n \) lines each contain a snack's name (a string without spaces) and its cost (an integer), separated by a space.

For example:

10
3
chips 5
soda 3
candy 2

outputFormat

Output a single line to standard output (stdout) containing the names of the snacks purchased, in the order they were dispensed (i.e. sorted by increasing cost), separated by a single space. If no snack can be purchased, output an empty line.

10
3
chips 5
soda 3
candy 2

candy soda chips