uva 990 wa

#include <stdio.h>

#define MAX(x, y) (x>y)?x:y

int t, w;
int n;
int d[1010], v[1010];
int check[1010];
int cnt = 0;
int track[1010][1010];

void inputCase()
{
    int i;
    scanf("%d", &t);
    scanf("%d", &w);
    scanf("%d", &n);

    for (i = 0; i < n; i++)
        scanf("%d%d", &d[i], &v[i]);
}

int solve(int time, int gold, int item)
{
    int x, y;

    if (item >= n)
    {
        track[item][time] = -1;
        return gold;
    }

    if (time == 0)
    {
        track[item][time] = -1;
        return gold;
    }

    if (time < 0)
    {
        track[item][time] = -1;
        return gold - v[item - 1];
    }

    x = solve(time, gold, item + 1);
    y = solve(time - (3 * w * d[item]), gold + v[item], item + 1);

    if (x > y)
    {
        track[item][time] = 2;
        return x;
    }
    else
    {
        track[item][time] = 1;
        return y;
    }
}


void printNum(int time, int item)
{
    if (item >= n)
        return ;

    if (time == 0)
        return ;

    if (time < 0)
        return;

    if (track[item][time] == 2)
        printNum(time, item + 1);
    else if (track[item][time] == 1)
    {
        cnt++;
        check[item] = 1;
        printNum(time - (3 * w * d[item]), item + 1);
    }
    else if (track[item][time] == -1)
    {
        return;
    }
}


int main()
{
    int i;

    inputCase();
    printf("%d\n", solve(t, 0, 0));

/*  for (i = 0; i < 10; i++)
    {
        if (check[i] == 1)
            cnt++;
    }
*/
    printNum(t, 0);
    printf("%d\n", cnt);
    for (i = 0; i < 40; i++)
    {
        if (check[i] == 1)
            printf("%d %d\n", d[i], v[i]);
    }
    return 0;
}