#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>

#define INT_MAX 2147483647

using namespace std;

ifstream fin("energii.in");
ofstream fout("energii.out");

struct generator
{
	int power;
	int requiredPower;
};

vector<generator> generators;

int solutions[1001][5001] = {};


void setInfinity(int w, int g)
{
	for (unsigned int i = 0; i < g; ++i)
	{
		for (unsigned int j = 0; j <= w; ++j)
		{
			solutions[i][j] = INT_MAX;
		}
	}
}


void dynamicProgramming(int w, int g)
{
	int powermax = 0;
	int val = INT_MAX;
	int cmax = 0;
	for (unsigned int i = 0; i < g; ++i)
	{
		for (unsigned int j = 0; j <= w; ++j)
		{
			if (i > 0)
			{
				val = solutions[i - 1][j];
			}
			else val = INT_MAX;
			if (j <= generators[i].power)
			{
				solutions[i][j] = min(generators[i].requiredPower, val);

			}
			else
			{
				if (generators[i].power + cmax >= j)
				{
					solutions[i][j] = powermax + min(generators[i].requiredPower, val);
				}
			}
		}
		cmax = generators[i].power;
		powermax += generators[i].requiredPower;
	}
}

int main()
{
	int power = 0, numberOfGenerators = 0;
	fin >> numberOfGenerators >> power;
	int max = INT_MAX;
	for (unsigned int i = 0; i < numberOfGenerators; ++i)
	{
		generator x;
		fin >> x.power;
		fin >> x.requiredPower;
		generators.push_back(x);
	}
	setInfinity(power, numberOfGenerators);
	dynamicProgramming(power, numberOfGenerators);

	for (unsigned int i = 0; i < numberOfGenerators; i++)
	{
		max = min(solutions[i][power], max);
	}
	fout << max;
	return 0;
}