http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=2627
/*
3 100
1 102
2 104
100 300
輸出：106
*/
#include<iostream>
#include<algorithm>
using namespace std;
struct Node
{
    int normalPrice;
    int magicPrice;
};
int main()
{
    int n,cost;
    while(cin>>n>>cost)
    {
        string str;
        Node infor[1001];
        int i,j,k,a,b,cc;
        char ch;
        for(cc=0,k=0,i=1;i<=n;i++)
        {
            cin>>a;
            ch=getchar();
            if(ch=='\n')//是換行符表示該行只有一個數
            {
                cc += a;
                continue;
            }
            else
            {                
                cin>>b;
                if(b-a>cost)//只能是有掙才會賣魔法價
                {
                    infor[k].normalPrice = a;
                    infor[k++].magicPrice = b;
                }
                else
                    cc += a;
            }
        }
        if(k==0 || cc >= cost)
        {
            for(i=0;i<k;i++)
                cc += infor[i].magicPrice;
            cc -= cost*k;
        }
        else
        {
            int temp;
            int remain = cost-cc;//購買鑒定卷軸欠缺的錢
            int *dp = new int[remain+1];//dp[i]表示還差i元錢時損耗的最小價值
            for(i=0;i<=remain;i++)
                dp[i]=100000000;
            dp[0] = 0;
            for(j=0;j<k;j++)//物品
            {
                temp = infor[j].magicPrice - infor[j].normalPrice - cost;//記得減去cost
                //temp表示虧損值
                if(infor[j].normalPrice >= remain && dp[remain] > temp )//正常價格夠買鑒定卷軸
                    dp[remain] = temp;
                else
                {
                    for( i=remain - infor[j].normalPrice ; i <= remain ; i++)
                    //i從remain - infor[j].normalPrice
                        if(dp[remain] > dp[i] + temp) 
                            dp[remain] = dp[i] + temp;
                    for( i=remain ; i >= infor[j].normalPrice ; i-- )
                        if(dp[i] > dp[i-infor[j].normalPrice] + temp)
                            dp[i] = dp[i-infor[j].normalPrice] + temp;
                }
            }
            if(dp[remain] == 100000000)//無法以魔法價格出售
            {
                for(i=0;i<k;i++)
                    cc += infor[i].normalPrice;
            }
            else
            {
                for(i=0;i<k;i++)
                    cc += infor[i].magicPrice;
                cc -= cost*k + dp[remain];//記得要扣掉買鑒定卷軸和損耗的錢
            }
        }
        cout<<cc<<endl;
    }
    return 0;
}