#include<iostream>
#include<stack>
#define N 200
using namespace std;
class HeapNode
{
    public:
        double uprofit,profit,weight;
        int level,x[N];
};

stack<HeapNode> H;
double w[N],p[N];
double cw,cp,c;
int n;

double Bound(int i)
{
    double cleft=c-cw,b=cp;
    while(i<=n&&w[i]<=cleft)
    {
        cleft-=w[i];
        b+=p[i];
        i++;
    }
    if(i<=n)  b+=p[i]/w[i]*cleft;
    return b;
}

void AddLiveNode(double up,double cp,double cw,bool ch,int level)
{
    HeapNode nod;
    nod.uprofit=up;
    nod.profit=cp;
    nod.weight=cw;
    nod.level=level;
    if(level<=n)  H.push(nod);
}

double Knap()
{
    int i=1;
    cw=cp=0;
    double bestp=0,up=Bound(1);
    while(1)
    {
        double wt=cw+w[i];
        if(wt<=c)
        {
            if(cp+p[i]>bestp)   bestp=cp+p[i];
            AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);
        }
        up=Bound(i+1);
        if(up>=bestp)
             AddLiveNode(up,cp,cw,false,i+1);
        if(H.empty())   return bestp;

        HeapNode node=H.top();
        H.pop();
        cw=node.weight;
        cp=node.profit;
        up=node.uprofit;
        i=node.level;
    }
}
int main()
{
    cout<<"请输入n和c:";  cin>>n>>c;
    cout<<"请输入w[i]"<<endl;
    for(int i=1;i<=n;i++)  cin>>w[i];

    cout<<"请输入p[i]"<<endl;
    for(int i=1;i<=n;i++)  cin>>p[i];

    cout<<"最优值是："<<Knap()<<endl;
    return 0;
}