UVa 990 - Diving for Gold

// UVa 990 - Diving for Gold

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

#define datatype signed long long int

int main() {
	int t, cases = 0;
	datatype w;
	while (cin >> t >> w) {
		cases++;
		int n;
		cin >> n;
		datatype d[30], v[30], c[30];
		for (int i = 0; i < n; i++) {
			cin >> d[i] >> v[i];
			c[i] = 3 * w * d[i];
		}
		datatype T[1001];
		bool R[30][1001];
		memset(R, false, sizeof(R));
		memset(T, 0, sizeof(T));
		for (int i = 0; i < n; i++) {
			for (datatype j = t - c[i]; j >= 0; j--) {
				if (T[j + c[i]] < T[j] + v[i]) {
					T[j + c[i]] = T[j] + v[i];
					R[i][j + c[i]] = true;
				}
			}
		}
		vector<int> seq;
		int s = t;
		for (int i = n - 1; i >= 0; i--) {
			if (R[i][s]) {
				seq.push_back(i);
				s -= c[i];
			}

		}
		sort(seq.begin(), seq.end());
		if (cases > 1)
			cout << endl;
		cout << T[t] << endl;
		cout << seq.size() << endl;
		for (int i = 0; i < seq.size(); i++)
			cout << d[seq[i]] << " " << v[seq[i]] << endl;

	}
	return 0;
}