#include <iostream>
#include <cstdio>

using namespace std;

int n, g;
int vec[1005];

void init_vec(int i, int elem)
{
    for(int j=g-i; j>=0; j--)
        if((vec[j]>0 || j==0 ) && vec[j+i] < vec[j] + elem)
            vec[j+i] = vec[j] + elem;
}

void read()
{
    int i, elem;
    scanf("%d %d\n", &n, &g);
    for(int k=1; k<=n; k++)
    {
        scanf("%d %d", &i, &elem);
        init_vec(i, elem);
    }
}

void afisare()
{
    int maxim = 0;
    for(int i=1; i<=g; i++)
        if(vec[i] > maxim)
            maxim = vec[i];
    printf("%d", maxim);

    for(int i=1,j=e;j<=n;i++,++j)
        {
            d[i][j]=INFINITY;
            for(int k=i;k<j;++k)
                d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]+v[i]*v[k+1]*v[j+1]);
        }
    t<<d[1][n];
}

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    read();
    afisare();
    return 0;
}