Challenge 12: Russell's Chocolate

Russell 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 Russell loves his chocolate bars (aka snipe bait), he needs to pack some in his little knapsack before he goes on his wilderness adventure. Being the chocolate connoisseur that he is, Russell has a variety of chocolate bars of varying levels of yumminess and in bars of different weights. Unfortunately, his bag only has a certain weight capacity, and he wants to maximize the total amount of yumminess of the chocolate he brings.

Therefore, you need to help him figure out what is the maximum amount of yumminess possible for the set of chocolate bars given a maximum weight capacity and which bars to pack.

Input

The input is a series of bag and bar specifications. The first line contains two numbers: the maximum weight capacity, and the number of bars in the set. This is followed by the bars 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.

Example Input

Output

For each bag and bar set, output the maximum level of yumminess possible considering the set of bars and the bag weight capacity, followed by the bars that should be packed in the bag to achieve this optimal chocolate yumminess level. The bars should be output in increasing order of weight, followed by yumminess.

Example Output

90
3 50
4 40

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa17-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge12               # Create and checkout challenge12 branch

$ $EDITOR challenge12/program.cpp           # Edit your code

$ git add challenge12/program.cpp           # Stage your changes
$ git commit -m "challenge12: done"         # Commit your changes

$ git push -u origin challenge12            # Send changes to GitLab

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge12 assignment ...
Submitting challenge12 code ...
  Result Success
   Score 6.00

$ curl -F source=@challenge12/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa17/challenge12
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 06 TA List to determine your corresponding TA for the merge request.