// En.cpp : Defines the entry point for the console application.
//
 
#include <stdio.h>
 
#define POSITION (curren + e[i] > W ? W : (curren + e[i]))
 
#define EN_LEVEL (e[i] > W ? W : e[i])
 
unsigned int G, W, e[1000], c[1000], mincost[5001], min = -1;
unsigned char available[5001][125];
 
int main()
{
    FILE *in, *out;
 
    unsigned int i, curren, j;
 
    if (!(in = fopen("energii.in", "r")))
        return -1;
 
    if (!fscanf(in, "%d %d", &G, &W))
        return -1;
 
    for (i = 0; i < G; ++i)
        if (!fscanf(in, "%d %d", &e[i], &c[i]))
            return -1;
 
    for (i = 0; i < G; ++i)
        if ((mincost[EN_LEVEL]>c[i]) || (!mincost[EN_LEVEL]))
        {
            mincost[EN_LEVEL] = c[i];
            for (j = 0; j < G / 8; ++j)
                available[EN_LEVEL][j] = 0xFF;
            available[EN_LEVEL][G / 8] = 0xFF << (8 - G%8);
            available[EN_LEVEL][i / 8] &= ~(1 << (7 - i % 8));
            if (((min == -1) || (min > mincost[EN_LEVEL])) && (e[i] >= W))
                min = mincost[EN_LEVEL];
        }
 
    for (curren = 1; curren < W;++curren)
        if (mincost[curren])
        {
            for (i = 0; i < G; ++i)
            {
                if ((available[curren][i / 8] & (1 << (7 - i % 8))) == (1 << (7 - i % 8)))
                    if ((mincost[POSITION]>mincost[curren] + c[i]) || (!mincost[POSITION]))
                    {
                        mincost[POSITION] = mincost[curren] + c[i];
                        for (j = 0; j < G / 8; ++j)
                            available[POSITION][j] = available[curren][j];
                        available[POSITION][G / 8] = available[curren][G / 8];
                        available[POSITION][i / 8] &= ~(1 << (7 - i % 8));
                        if (((min == -1) || (min > mincost[POSITION])) && (curren + e[i] >= W))
                            min = mincost[POSITION];
                    }
            }
        }
 
    if (!(out = fopen("energii.out", "w")))
        return -1;
 
    if (!fprintf(out, "%d", min))
        return -1;
 
    return 0;
}