#include <iostream>
#include <vector>

using namespace std;

//类似于背包问题，代码逻辑的话和0 - 1背包不同的主要是1.总体积(本题是铁矿石大小)可以超出容量 2.可以选择一个物品升级
//针对超出容量我们只需要把dp[i][j] = j >= w[i] ? max(dp[i - 1][j], dp[i][j - w[i]] + v[i]) : dp[i - 1][j]改一下改成j > 0时dp[i][j] = min(j - w[i] > 0 ? dp[i - 1][j - w[i]] + v[i] : v[i], dp[i - 1][j])表示只要j > 0就可以拿物品， 且j <= 0时dp[i][j] = 0，这是因为满足熔炼矿石之后没必要继续了;
//对于可以升级的问题，想过一开始能不能转成多重背包，或者中间修改一个flag的方式好像都不行，就尝试添加一个状态维度
//最后是需要注意的点 1.精度，且最小化问题初始值是一个足够大的数字10 ^ 6 * 10 ^ 9至少 2.使用滚动数组的需要注意先更新dp[j][1]再更新dp[j][0],因为dp[j][1]依赖于dp[j][0], 还有点疑问按道理n * m的复杂度对于m和n都是10 ^ 6不会超时吗
int main() {
	int n, m;
	cin >> n >> m;
	long long** dp = new long long*[m + 1];
	for (int i = 0; i <= m; i++) {
		dp[i] = new long long[2];
		dp[i][0] = 1e16;
		dp[i][1] = 1e16;
	}
	int *w = new int[n + 1], *v = new int[n + 1];
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> v[i];
	}
	for(int i = 1; i <= n; i++) {
		for (int j = m; j >= 1; j--) {
		  //状态转移方程
			dp[j][1] = min(min(dp[j][1], j - w[i] > 0 ? dp[j - w[i]][1] + v[i] : v[i]), j - 2 * w[i] > 0 ? dp[j - 2 * w[i]][0] + v[i] / 2 : v[i] / 2);
			dp[j][0] = min(dp[j][0], j - w[i] > 0 ? dp[j - w[i]][0] + v[i] : v[i]);
		}
	}
	cout << dp[m][1] << endl;
}