#include <iostream>
#include <stdio.h>
using namespace std;
int расходы [10000000];

int main() {
    //freopen ("energii.in", "r", stdin);
    //freopen ("energii.out", "w", stdout);

    int нагрузка, максимальная;
    int Стоимость, энергия;
    cin >> нагрузка >> максимальная;

    for (int i = 1; i <= нагрузка; i++) {
        cin >> Стоимость >> энергия;
        for (int i = энергия - 1; i >= 0; i--) {
            if (расходы [i] > 0 && i + Стоимость >= энергия)
                расходы [i + Стоимость] = расходы
        }
    }
}