#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;

int c[5010];
int g, w;

int main (void) {
	freopen("energii.in", "r", stdin);
	freopen("energii.out", "w", stdout);
	
	scanf("%d", &g);
	scanf("%d", &w);
	
	memset(c, 999999, (w+1) * sizeof(int));
	
	int ei, ci;
	for (int i = 0; i < g; ++i) {
		scanf("%d %d", &ei, &ci);
		if (ei >= w) {
			c[w] = min(c[w], ci);
		} else {
			c[ei] = min(c[ei], ci);
		}
	}
	
	for (int i = 1; i <= w; ++i) {
		for (int j = i - 1; j >= 1; --j) {
			c[i] = min(c[i], c[i - j] + c[j]);
		}
	}
	
	printf("%d", c[w]);
	
	return 0;
}