/*
TASK: lift
LANG: C++
*/

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

#define MAX 1024
#define MM 131072
#define INF 999666333
#define in cin
#define out cout

using namespace std;

//ifstream(in); ofstream(out);
int n, m, ans;
int a[MAX][2];
int dyn[MM][2];

int recurse(int msk, int sd, int w, int p)
{
int i, c;
int cur, best;

//out << "side " << sd << " with mask: " << msk << " price " << p << " and weight " << w << endl;

if (msk == 0 && sd == 0) return INF;
if (msk == 0 && sd == 1) return 0;
if (w == 0 && p == 0 && dyn[msk][sd] != -1) return dyn[msk][sd];
if (w == 0 && p == 0) dyn[msk][sd] = INF;

best = INF;

if (sd == 0)
   {
   for (i=0; i<n; i++) if ((msk & (1 << i)) > 0 && (w + a[i][1] <= m))
       {
       if (a[i][0] > p) c = a[i][0];
       else c = p;
       
       cur = recurse(msk ^ (1 << i), 1, 0, 0) + c;
       if (best > cur) best = cur;
       
       cur = recurse(msk ^ (1 << i), 0, w+a[i][1], c);
       if (best > cur) best = cur;
       }
   }
else
   {
   for (i=0; i<n; i++) if ((msk & (1 << i)) == 0 && (w + a[i][1] <= m))
       {
       if (a[i][0] > p) c = a[i][0];
       else c = p;
       
       cur = recurse(msk ^ (1 << i), 0, 0, 0) + c;
       if (best > cur) best = cur;

       cur = recurse(msk ^ (1 << i), 1, w+a[i][1], c);
       if (best > cur) best = cur;
       }   
   }

if (w == 0 && p == 0) dyn[msk][sd] = best;

//out << "Side " << sd << " with mask " << msk << " has best ans " << best << endl;

return best;
}


int main(void)
{
int i;

//in.open("lift.in"); out.open("lift.out");

memset(a, 0, sizeof(a));
memset(dyn, -1, sizeof(dyn));
ans = INF;

in >> n >> m;
for (i=0; i<n; i++) in >> a[i][0] >> a[i][1];


ans = recurse((1 << n) - 1, 0, 0, 0);

if (ans == INF) ans = 0;
out << ans << endl;

return 0;
}
