using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3 10");
WillReturn.Add("15 9");
WillReturn.Add("10 6");
WillReturn.Add("6 4");
//16
}
else if (InputPattern == "Input2") {
WillReturn.Add("30 499887702");
WillReturn.Add("128990795 137274936");
WillReturn.Add("575374246 989051853");
WillReturn.Add("471048785 85168425");
WillReturn.Add("640066776 856699603");
WillReturn.Add("819841327 611065509");
WillReturn.Add("704171581 22345022");
WillReturn.Add("536108301 678298936");
WillReturn.Add("119980848 616908153");
WillReturn.Add("117241527 28801762");
WillReturn.Add("325850062 478675378");
WillReturn.Add("623319578 706900574");
WillReturn.Add("998395208 738510039");
WillReturn.Add("475707585 135746508");
WillReturn.Add("863910036 599020879");
WillReturn.Add("340559411 738084616");
WillReturn.Add("122579234 545330137");
WillReturn.Add("696368935 86797589");
WillReturn.Add("665665204 592749599");
WillReturn.Add("958833732 401229830");
WillReturn.Add("371084424 523386474");
WillReturn.Add("463433600 5310725");
WillReturn.Add("210508742 907821957");
WillReturn.Add("685281136 565237085");
WillReturn.Add("619500108 730556272");
WillReturn.Add("88215377 310581512");
WillReturn.Add("558193168 136966252");
WillReturn.Add("475268130 132739489");
WillReturn.Add("303022740 12425915");
WillReturn.Add("122379996 137199296");
WillReturn.Add("304092766 23505143");
//3673016420
}
else if (InputPattern == "Input3") {
WillReturn.Add("10 2921");
WillReturn.Add("981421680 325");
WillReturn.Add("515936168 845");
WillReturn.Add("17309336 371");
WillReturn.Add("788067075 112");
WillReturn.Add("104855562 96");
WillReturn.Add("494541604 960");
WillReturn.Add("32007355 161");
WillReturn.Add("772339969 581");
WillReturn.Add("55112800 248");
WillReturn.Add("98577050 22");
//3657162058
}
else if (InputPattern == "Input4") {
WillReturn.Add("10 936447862");
WillReturn.Add("854 810169801");
WillReturn.Add("691 957981784");
WillReturn.Add("294 687140254");
WillReturn.Add("333 932608409");
WillReturn.Add("832 42367415");
WillReturn.Add("642 727293784");
WillReturn.Add("139 870916042");
WillReturn.Add("101 685539955");
WillReturn.Add("853 243593312");
WillReturn.Add("369 977358410");
//1686
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long mN;
static long mW;
struct ItemInfoDef
{
internal long Val;
internal long Omosa;
}
static List<ItemInfoDef> mItemList = new List<ItemInfoDef>();
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = (pStr) =>
wkArr = pStr.Split(' ').Select(X => long.Parse(X)).ToArray();
SplitAct(InputList[0]);
mN = wkArr[0];
mW = wkArr[1];
bool WillSolve2 = true;
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
ItemInfoDef WillAdd;
WillAdd.Val = wkArr[0];
WillAdd.Omosa = wkArr[1];
if ((1 <= WillAdd.Omosa && WillAdd.Omosa <= 1000) == false) {
WillSolve2 = false;
}
// 重すぎる荷物はAddしない
if (WillAdd.Omosa <= mW) {
mItemList.Add(WillAdd);
}
}
if (mN <= 30) Solve1();
else if (WillSolve2) Solve2();
else Solve3();
}
struct ResultDef
{
internal long SumVal;
internal long SumOmosa;
}
// N <= 30の場合は、半分全探索
static void Solve1()
{
int UB = mItemList.Count - 1;
int UBHalf = UB / 2;
var ZenhanItemList = new List<ItemInfoDef>();
var KouhanItemList = new List<ItemInfoDef>();
for (int I = 0; I <= UBHalf; I++) {
ZenhanItemList.Add(mItemList[I]);
}
for (int I = UBHalf + 1; I <= UB; I++) {
KouhanItemList.Add(mItemList[I]);
}
int ZenhanCompleteBit = (1 << ZenhanItemList.Count);
int KouhanCompleteBit = (1 << KouhanItemList.Count);
var ZenhanResultList = new List<ResultDef>();
var KouhanResultList = new List<ResultDef>();
for (int I = 0; I <= ZenhanCompleteBit; I++) {
long SumVal = 0;
long SumOmosa = 0;
for (int J = 0; J <= ZenhanItemList.Count - 1; J++) {
if ((I & (1 << J)) > 0) {
SumVal += ZenhanItemList[J].Val;
SumOmosa += ZenhanItemList[J].Omosa;
if (SumOmosa > mW) break;
}
}
if (SumOmosa <= mW) {
ResultDef WillAdd;
WillAdd.SumVal = SumVal;
WillAdd.SumOmosa = SumOmosa;
ZenhanResultList.Add(WillAdd);
}
}
for (int I = 0; I <= KouhanCompleteBit; I++) {
long SumVal = 0;
long SumOmosa = 0;
for (int J = 0; J <= KouhanItemList.Count - 1; J++) {
if ((I & (1 << J)) > 0) {
SumVal += KouhanItemList[J].Val;
SumOmosa += KouhanItemList[J].Omosa;
if (SumOmosa > mW) break;
}
}
if (SumOmosa <= mW) {
ResultDef WillAdd;
WillAdd.SumVal = SumVal;
WillAdd.SumOmosa = SumOmosa;
KouhanResultList.Add(WillAdd);
}
}
// 重さの昇順にソートしておく
ZenhanResultList.Sort((A, B) => A.SumOmosa.CompareTo(B.SumOmosa));
KouhanResultList.Sort((A, B) => A.SumOmosa.CompareTo(B.SumOmosa));
long ZenhanMax = ZenhanResultList.Max(X => X.SumVal);
long KouhanMax = KouhanResultList.Max(X => X.SumVal);
long MaxSumVal = Math.Max(ZenhanMax, KouhanMax);
foreach (ResultDef EachZenhan in ZenhanResultList) {
if (EachZenhan.SumVal + KouhanMax <= MaxSumVal) {
continue;
}
foreach (ResultDef EachKouhan in KouhanResultList) {
if (EachZenhan.SumOmosa + EachKouhan.SumOmosa > mW)
break;
long wkSumVal = EachZenhan.SumVal + EachKouhan.SumVal;
if (MaxSumVal < wkSumVal)
MaxSumVal = wkSumVal;
}
}
Console.WriteLine(MaxSumVal);
}
// 全ての荷物の重さが1000以下の場合
static void Solve2()
{
long UB = mW;
// 価値合計の最大値[重さ合計]のDP表
long?[] DPArr = new long?[UB + 1];
DPArr[0] = 0;
foreach (ItemInfoDef EachItem in mItemList) {
for (long I = UB - EachItem.Omosa; 0 <= I; I--) {
if (DPArr[I].HasValue == false) continue;
long NewInd = I + EachItem.Omosa;
long NewVal = DPArr[I].Value + EachItem.Val;
if (DPArr[NewInd].HasValue) {
if (DPArr[NewInd].Value >= NewVal) {
continue;
}
}
DPArr[NewInd] = NewVal;
}
}
Console.WriteLine(DPArr.Max());
}
// 全ての荷物の価値が1000以下の場合
static void Solve3()
{
//最小の重さ[価値合計]のDP表
var PrevDP = new Dictionary<long, long>();
PrevDP[0] = 0;
foreach (ItemInfoDef EachItem in mItemList) {
var CurrDP = new Dictionary<long, long>(PrevDP);
foreach (var EachPair in PrevDP) {
long EachKey = EachPair.Key;
long NewVal = EachPair.Value + EachItem.Omosa;
//重さ制限を超えてしまう場合
if (NewVal > mW) continue;
long NewKey = EachKey + EachItem.Val;
if (CurrDP.ContainsKey(NewKey)) {
if (CurrDP[NewKey] <= NewVal) {
continue;
}
}
CurrDP[NewKey] = NewVal;
}
PrevDP = CurrDP;
}
Console.WriteLine(PrevDP.Keys.Max());
}
}