/*------------------------------------------------------------------------------
 * problem016.c: Jenny Cub's Knapsack
**----------------------------------------------------------------------------*/

/* Copyright (c) 2009 Peter Bui. All Rights Reserved.
 *
 * Peter Bui <pbui@cse.nd.edu>
 *
**------------------------------------------------------------------------------
 * Includes
**----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*------------------------------------------------------------------------------
 * Data Structures
**----------------------------------------------------------------------------*/

struct jar 
{
    int weight;
    int yumminess;
};

/*------------------------------------------------------------------------------
 * Constants
**----------------------------------------------------------------------------*/

#define TRUE	    1
#define FALSE	    0
#define NMAX_JARS   20
#define NMAX_WEIGHT 20

/*------------------------------------------------------------------------------
 * Global Variables
**----------------------------------------------------------------------------*/
    
static int Y[NMAX_JARS + 1][NMAX_WEIGHT + 1]; // Yumminess table
static int K[NMAX_JARS + 1][NMAX_WEIGHT + 1]; // Keep table

/*------------------------------------------------------------------------------
 * Functions
**----------------------------------------------------------------------------*/

static int
read_jars(struct jar jars[], int *max_weight, int *njars)
{
    int j;
    
    scanf("%d %d", max_weight, njars);

    if (*max_weight == 0 && *njars == 0)
	return (FALSE);

    memset(jars, 0, sizeof(struct jar) * (NMAX_JARS + 1));
    for (j = 1; j <= *njars; j++) 
	scanf("%d %d", &jars[j].weight, &jars[j].yumminess);

    return (TRUE);
}

/*----------------------------------------------------------------------------*/

inline int
max(int a, int b)
{
    return ((a > b) ? a : b);
}

/*----------------------------------------------------------------------------*/

static void
compute_tables(struct jar jars[], int max_weight, int njars)
{
    int j, w;

    memset(Y, 0, sizeof(int) * (NMAX_JARS + 1) * (NMAX_WEIGHT + 1));
    memset(K, 0, sizeof(int) * (NMAX_JARS + 1) * (NMAX_WEIGHT + 1));

    for (j = 1; j <= njars; j++) {
	for (w = 1; w <= max_weight; w++) {
	    if (jars[j].weight <= w) 
		Y[j][w] = max(Y[j - 1][w], jars[j].yumminess + Y[j - 1][w - jars[j].weight]);
	    else 
		Y[j][w] = Y[j - 1][w];
	    K[j][w] = (Y[j][w] != Y[j - 1][w]);
	}
    }

    /* Print tables for debugging
    for (j = 0; j <= njars; j++) {
	for (w = 0; w <= max_weight; w++) 
	    printf("%02d ", Y[j][w]);
	putchar('\n');
    }
    for (j = 0; j <= njars; j++) {
	for (w = 0; w <= max_weight; w++) 
	    printf("%02d ", K[j][w]);
	putchar('\n');
    }*/
}

/*----------------------------------------------------------------------------*/

static int
cmp_jars(const void *a, const void *b)
{
    struct jar *ja = (struct jar*)(a);
    struct jar *jb = (struct jar*)(b);
    int result = 0;

    result = (ja->weight - jb->weight);
    if (result == 0)
	result = (ja->yumminess - jb->yumminess);

    return (result);
}

/*----------------------------------------------------------------------------*/

static void
extract_jars(struct jar oj[], struct jar sj[], int max_weight, int njars)
{
    int s, j, w;
    
    memset(sj, 0, sizeof(struct jar) * NMAX_JARS);
	
    w = max_weight;
    s = 1;
    for (j = njars; j >= 0; j--) {
	if (K[j][w]) {
	    memcpy(&sj[s++], &oj[j], sizeof(struct jar));
	    w -= oj[j].weight;
	}
    }

    qsort(sj, s, sizeof(struct jar), cmp_jars);
}

/*------------------------------------------------------------------------------
 * Main Execution
**----------------------------------------------------------------------------*/

int
main(int argc, char* argv[]) 
{
    struct jar all_jars[NMAX_JARS + 1];
    struct jar sel_jars[NMAX_JARS + 1];
    int max_weight, njars, j;

    while (read_jars(all_jars, &max_weight, &njars)) {
	compute_tables(all_jars, max_weight, njars);
	extract_jars(all_jars, sel_jars, max_weight, njars);
	
	printf("%d\n", Y[njars][max_weight]);
	for (j = 1; sel_jars[j].weight; j++)
	    printf("%d %d\n", sel_jars[j].weight, sel_jars[j].yumminess);
    }

    return (EXIT_SUCCESS);
}

/*------------------------------------------------------------------------------
 * vim: sts=4 sw=4 ts=8 ft=c
**----------------------------------------------------------------------------*/