// за дадени n елемента с цени и обеми и раница с капацитет W се търси максималната печалба за време O(n*W)

#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> pr;

const int n = 10, MaxCap = 1000;

int memo[n][MaxCap];

pr a[n] = { pr(7, 1), pr(13, 2), pr(1, 6), pr(12, 8), pr(8, 4), pr(6, 3), pr(5, 7), pr(14, 6), pr(4, 5), pr(2, 6) };

// максимална печалба от елемент i нататък за капацитет c
int win(int i, int c)
{
	if (i == n) return 0;
	if (memo[i][c] != -1) return memo[i][c];
	if (a[i].second > c) return memo[i][c] = win(i + 1, c);
	return memo[i][c] = max(win(i + 1, c), win(i + 1, c - a[i].second) + a[i].first);
}

int main()
{
	for (int i = 0; i < n; i++)for (int j = 0; j < MaxCap; j++) memo[i][j] = -1;

	int W = 27;

	cout << win(0, W) << endl;

	for (int i = 0; i < n; i++) if (win(i,W) == win(i + 1, W - a[i].second) + a[i].first)
	{
		cout << "(" << a[i].first << ", " << a[i].second << ") ";
		W -= a[i].second;
	}

	cout << endl;

	return 0;
}