Description

Despite the rather inclement weather, Jenny Cub is taking her little sheep Baa-ba on a camping trip to Roseland Park. She has just finished watching the PBS special National Parks: America's Best Idea by Ken Burns and is ready for some wild and outdoor fun!

Of course, since Jenny Cub loves her honey, she needs to pack some in her little knapsacks before she goes on her wilderness adventure. Being the honey connoisseur that she is, Jenny Cub has a variety of honey of varying levels of yumminess and in jars of different weights. Unfortunately, her bags only have a certain weight capacity, and she wants to maximize the total amount of yumminess of the honey she brings. Therefore, you need to help her figure out what is the maximum amount of yumminess possible for the set of honey jars given a maximum weight capacity and which jars to pack.

Input

The input is a series of bag and jar specifications. The first line contains two numbers: the maximum weight capacity, and the number of jars in the set. This is followed by the jars themselves, each on their own line, first specifying the weight, followed by the yumminess. You can assume all these numbers are integers. The end of the input will be denoted by 0 0. Here is an sample input:

10 4
5 10
4 40
6 30
3 50
0 0

Output

For each bag and jar set, output the maximum level of yumminess possible considering the set of jars and the bag weight capacity, followed by the jars that should be packed in the bag to achieve this optimal honey yumminess level. The jars should be output in increasing order of weight, followed by yumminess. Here is an sample output:

90
3 50
4 40

Approach

Use dynamic programming to build a table as suggested here.

Input/Output

• Final Input: problem016.input
• Final Output: problem016.output

Source Code

• Peter Bui's source code: pbui.c
• Noah Franske's source code: nfranske.cc
• Raymond LeGrand's source code: rlegrand.cc