#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using std::cin, std::cout, std::endl;
using std::fstream;
using std::max;
using std::ostream;
using std::sort;
using std::vector;

using LL = long long;
const char endq = '\n';

class ItemInfo
{
public:
    LL limit1;
    LL limit2;
    LL value;
    bool putIntoBag;

    ItemInfo(LL limit1, LL limit2, LL value)
        : limit1(limit1),
          limit2(limit2),
          value(value),
          putIntoBag(false) {}

    friend ostream &operator<<(ostream &os, const ItemInfo &item);
};

vector<ItemInfo> readItemsFromFile()
{
    fstream inputFile;

    // open file and check if valid
    inputFile.open("./in.txt", std::ios::in);
    if (!inputFile.is_open())
    {
        cout << "Failed to open file in.txt" << endq;
        exit(-1);
    }

    LL itemCount;
    LL limit1, limit2, value;
    vector<ItemInfo> itemsArr;

    inputFile >> itemCount;

    for (LL i = 0; i < itemCount; ++i)
    {
        inputFile >> limit1 >> limit2 >> value;
        itemsArr.emplace_back(ItemInfo(limit1, limit2, value));
    }

    inputFile.close();

    return itemsArr;
}

ostream &operator<<(ostream &os, const ItemInfo &item)
{
    os << "<ItemInfo limit1:" << item.limit1 << " limit2:" << item.limit2 << " value:" << item.value << ">";
    return os;
}

void writeAnswerIntoFile(LL ans)
{
    fstream outputFile;
    outputFile.open("./out.txt", std::ios::out);
    outputFile << ans;
    outputFile.close();
}

LL dpArr[10][1000][1000] = {0};
LL calculateMaxValue(vector<ItemInfo> itemArr, LL maxLimit1, LL maxLimit2)
{
    ItemInfo currentItem(0, 0, 0);
    for (LL i = 0; i <= itemArr.size(); ++i)
    {
        for (LL j = 0; j <= maxLimit1; ++j)
        {
            for (LL k = 0; k <= maxLimit2; ++k)
            {

                if (i == 0)
                {
                    dpArr[i][j][k] = 0;
                    continue;
                }

                currentItem = itemArr[i - 1];
                LL valueWhenNotChoosingThis = dpArr[i - 1][j][k];
                LL valueWhenChoosingThis = dpArr[i - 1][j][k];
                if (j >= currentItem.limit1 && k >= currentItem.limit2)
                {
                    valueWhenChoosingThis = dpArr[i - 1][j - currentItem.limit1][k - currentItem.limit2] + currentItem.value;
                }
                dpArr[i][j][k] = max(valueWhenChoosingThis, valueWhenNotChoosingThis);
            }
        }
    }

    return dpArr[itemArr.size()][maxLimit1][maxLimit2];
}

// Check the final situation, determine if an item has been put into the bag
void getSolutionSet(vector<ItemInfo> &items, LL maxLimit1, LL maxLimit2)
{
    LL size = items.size();
    LL curLimit1 = maxLimit1;
    LL curLimit2 = maxLimit2;

    cout << "Put into bag: " << endq;
    for (LL currentItem = size; currentItem > 0; --currentItem)
    {
        if (dpArr[currentItem - 1][curLimit1][curLimit2] != dpArr[currentItem][curLimit1][curLimit2])
        {
            cout << items[currentItem - 1] << endq;
            items[currentItem - 1].putIntoBag = true;
            curLimit1 -= items[currentItem - 1].limit1;
            curLimit2 -= items[currentItem - 1].limit2;
        }
    }
}

int main()
{
    LL maxLimit1 = 2;
    LL maxLimit2 = 2;

    vector<ItemInfo> itemArr = readItemsFromFile();
    // here you can change the max limit 1 and max limit 2
    LL ans = calculateMaxValue(itemArr, maxLimit1, maxLimit2);
    getSolutionSet(itemArr, maxLimit1, maxLimit2);
    writeAnswerIntoFile(ans);
    return 0;
}