#include <bits/stdc++.h>

using namespace std;

struct GoiHang {
	int w; //trong luong
	int v; //gia tri
};

GoiHang gh[] = {
	{0, 0}, {1, 2},
	{3, 4}, {5, 6},
	{7, 8}, {9, 10},
	{11, 12},
};

int n = 6, m = 10;
int F[7][11];

void CaiTui() {
	for (int j = 0; j <= m; j++) F[0][j] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			F[i][j] = F[i - 1][j];
			int temp = F[i - 1][j - gh[i].w] + gh[i].v;
			if (gh[i].w <= j && F[i][j] < temp) F[i][j] = temp;
		}
	}
}

void TruyVet() {
	cout << "Gia tri lon nhat la: " << F[n][m] << endl;
	int i = n; int j = m;
	cout << "Goi\tKhoi luong\tGia tri" << endl;
	while (i != 0) {
		if (F[i][j] != F[i - 1][j]) {
			cout << i << "\t" << gh[i].w << "\t\t" << gh[i].v << endl;;
			j = j - gh[i].w;
		}
		i--;
	}
}

int main() {
	CaiTui();
	TruyVet();
	return 0;
}