#include <cstdio>
#define max(a, b) ((a > b) ? a : b)

struct Item {
    int profit, weight;
};

int n, Wmax, i, w, dp[2][10001] {};
Item v[5001];

int main() {
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    scanf("%d%d", &n, &Wmax);
    for(i = 1; i <= n; ++i)
        scanf("%d%d", &v[i].weight, &v[i].profit);
    
    for(i = 1; i <= n; ++i)
        if(i % 2 == 0)
            for(w = v[i].weight; w <= Wmax; ++w)
                if(v[i].weight <= w)
                    dp[0][w] = max(dp[1][w], dp[1][w-v[i].weight] + v[i].profit);
                else
                    dp[0][w] = dp[1][w];
        else
            for(w = v[i].weight; w <= Wmax; ++w)
                if(v[i].weight <= w)
                    dp[1][w] = max(dp[0][w], dp[0][w-v[i].weight] + v[i].profit);
                else
                    dp[1][w] = dp[0][w];  

    printf("%d ", dp[(i-1) % 2][w-1]);
}