#include <iostream>
#include <fstream>
#define gmax 1005
#define wmax 5005
#define inf 999999999
using namespace std;

int dp[gmax][wmax];

int main() {
	ifstream f("energii.in");
	ofstream g("energii.out");
	
	int G, N, i, j, w[10005], p[10005];
	
	f>>N>>G;
	
	for(i=1; i<=N; i++) {
		f>>p[i]>>w[i];
	}
	
	for(i=0; i<=N; i++) 
		for(j=0; j<=G; j++)
			dp[i][j]=inf;
	
	for(i=1; i<=N; i++) {
		for(j=0; j<=G; j++) {
			
			dp[i][j] = min( dp[i-1][j], w[i] );
			
			if(w[i] <= j) {
				dp[i][j] = min( dp[i-1][j], p[i] + dp[i-1][j-p[i]] );
			}
			
		}
	}
	
	for(i=0; i<=N; i++) {
		for(j=1; j<=G; j++) {
			g<<dp[i][j]<<" ";
		}
		g<<"\n";
	}

	if(dp[N][G]==inf) dp[N][G] = -1;
	
	g<<dp[N][G]<<"\n";
	
	f.close();
	g.close();
	return 0;
}