gistfile1.cpp

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <functional>
#include <cmath>
#include <math.h>

#define lli long long int

using namespace std;

lli ans;

struct Element {
    int h;
    int count;
};

struct Assembly {
    int h;
    int count;

    bool operator<(const Assembly & that) const {
        if (h != that.h) return h < that.h;
        return count < that.count;
    }

    Assembly(int _h, int _count) {
        h = _h;
        count = _count;
    }

};

lli needHeigth;

const int MAX_COUNT = 10;

int main() {
    int n;
    cin >> n >> needHeigth;
    vector<Element> elements(n);
    for(int i = 0; i < n; ++i) {
        cin >> elements[i].h >> elements[i].count;
    }
    set<Assembly> allSums;
    for(int i = 0; i < elements.size(); ++i) {
        Element el = elements[i];
        set<Assembly> currentSet;
        int maxCount = min(el.count, MAX_COUNT);
        Assembly assembly = Assembly(el.h, 1);
        allSums.insert(assembly);        
        for(set<Assembly>::iterator it = allSums.begin(); it != allSums.end(); ++it) {
            for(int k = 0; k <= maxCount; ++k) {
                if (it->h + k * el.h > needHeigth) break;
                Assembly newAssembly = Assembly(it->h + k * el.h, it->count + k);
                currentSet.insert(newAssembly);
            }
        }        
        allSums = currentSet;
    }
    set<Assembly>::iterator it = allSums.lower_bound(Assembly(needHeigth, 0));
    if (it == allSums.end() || it->h != needHeigth) {
        cout << "No solution";
    } else {
        cout << it->h << " " << it->count << endl;        
    }
    return 0;
}