// En.cpp : Defines the entry point for the console application.
//

#include <stdio.h>

#define POSITION (curren + e[i] > W ? W : (curren + e[i]))

#define MAXPOS (e[i] > W ? W : e[i])

unsigned int G, W, e[1000], c[1000];
unsigned long long 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[MAXPOS]>c[i]) || (!mincost[MAXPOS]))
        {
            mincost[MAXPOS] = c[i];
            for (j = 0; j < G / 8; ++j)
                available[MAXPOS][j] = 0xFF;
            available[MAXPOS][G / 8] = 0xFF << (8 - G%8);
            available[MAXPOS][i / 8] &= ~(1 << (7 - i % 8));
            if (((min == -1) || (min > mincost[MAXPOS])) && (e[i] >= W))
                min = mincost[MAXPOS];
        }

    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;
}