/* maximalni pocet predmetu v zadani */
#define MAXITEMS 1000

/* maximalni nosnost */
#define MAXWEIGHT 100000

/* trida pro jeden item */
class CItem {
    public:
        int cost;
        int weight;
        CItem(int tcost, int tweight): cost(tcost), weight(tweight) {}
        CItem() {cost = weight = 0;}
};

/* trida pro mnozinu itemu a vlastnosti batohu */
class CKnapSack {
    private:
        int n;
        CItem item[MAXITEMS];
        int in_sack[MAXITEMS];
        int maxweight;
        int weight;
        int cost;

    public:
        CKnapSack() {
            n = weight = cost = 0;
            maxweight = 0;
            for(int i = 0; i < MAXITEMS; i++) in_sack[i] = 0;
        }

        // vynuluj batoh
        void clear() {
            n = weight = cost = 0;
            for(int i = 0; i < MAXITEMS; i++) in_sack[i] = 0;
        }

        // nastav nosnost batohu
        int setMaxWeight(int tmaxweight) {
            if(tmaxweight < 0) return 0;
            maxweight = tmaxweight;
            return 1;
        }

        // zjisti nosnost batohu
        int getMaxWeight() {
            return maxweight;
        }

        // zjisti hmotnost veci v batohu
        int getWeight() {
            return weight;
        }

        // zjisti cenu veci v batohu
        int getCost() {
            return cost;
        }

        // vloz i-ty item do batohu (reseni)
        int putInSack(int i) {
           if(i < 0 || i >= n) return 0;
           if(!in_sack[i]) {
                weight += item[i].weight;
                cost += item[i].cost;
           }
           in_sack[i] = 1;
           return 1;
        }

        // vyndej i-ty item z batohu (reseni)
        int getFromSack(int i) {
           if(i < 0 || i >= n) return 0;
           if(in_sack[i]) {
                weight -= item[i].weight;
                cost -= item[i].cost;
           }
           in_sack[i] = 0;
           return 1;
        }

        // je i-ty item v batohu (reseni)?
        int isInSack(int i) {
           if(i < 0 || i >= n) return 0;
           return in_sack[i];
        }

        // vyndej vse z batohu (reseni)
        void emptySack() {
           for(int i = 0; i < MAXITEMS; i++) in_sack[i] = 0;
           weight = cost = 0;
        }

        // vloz item do mnoziny itemu
        int addItem(int cost, int weight) {
            if(n == MAXITEMS) return 0;
            item[n++] = CItem(cost, weight);
            return 1;
        }

        // vrat i-ty predmet
        CItem getItem(int i) {
            return item[i];
        }

        // vrat pocet predmetu
        int getItems() {
            return n;
        }
};