E题：来硬的（C++解法：01背包）

详解看代码！！！

#include<bits/stdc++.h>
using namespace  std;
const int N = 1e6+10;
#define ll long long
ll x[N],y[N];
ll n,m;
ll f[N][2];
/*
    本题的f[i][j]表示融化i单位的铁矿石，是否已经使用了暗物质（j=0表示没有使用，j=1表示已经或者本次使用）        
    1.01背包的思路，再一维优化的基础上i，二维上就是是否使用暗物质j
    2.本题有一个坑，至多融化x单位的铁矿石，所以j要从m遍历到0，然后对f[i][max(0ll,j-v[i])]取一个max,  
*/

int main()
{
    cin>>n>>m;
    for(ll i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=m;j>=0;j--)
        {
            //由于至多x单位的铁矿石，所以x[i]可能大于m，这也是合法的答案，可以计入f[0][0gtt]
            //还没有使用暗物质所以f[j][0]，就正常转移
            f[j][0]=min(f[j][0],f[max(0ll,j-x[i])][0]+y[i]);
            //已经使用过暗物质了所以f[j][1]
            f[j][1]=min(f[j][1],f[max(0ll,j-x[i])][1]+y[i]);
            //还没有使用过暗物质，对于第i个煤炭使用暗物质
            f[j][1]=min(f[j][1],f[max(0ll,j-2*x[i])][0]+y[i]/2);
        }
    }
    cout<<min(f[m][0],f[m][1]);
    
    return 0;
}