#include <iostream>
using namespace std;
//w是物品重量，p是物品价值,c是物品最多能拿的数量，m键物品，总重weight
int w[30],p[30],c[30],m,weight;
int dp[30]; //dp[用了多少体积]=用多少体积得到最大价值
//dp[看到第几个物品][装了多少体积的物品]=前面条件下的最大价值
int main() {
	cin>>weight>>m; //weight是背包体积，m是物品数
	for (int i=1;i<=m;i++)
		cin>>w[i];	//各个物品的体积
	for (int i=1;i<=m;i++)
		cin>>p[i];	//各个物品的价值
	for (int i=1;i<=m;i++)
		cin>>c[i];	//各个物品的数量
	//枚举第I个物品，体积Wi 价值Pi 数量Ci
	for (int i=1;i<=m;i++) {
		int d=1,cnt=c[i]; 
		//有cnt个物品没用，打算将其中d个分出来
		while (cnt>0) { //没分完
			if (cnt>=d) 
				cnt-=d; //如果刚好能拿D个
			else { //如果D比cnt大，那么就剩下多少为
				d=cnt; //一次数量的划分
				cnt=0;
			} //当前一堆的体积，当前一堆的价值
			int wp=w[i]*d,vp=p[i]*d;
			for (int j=weight;j>=wp;j--) //保证体积j比WP大
				dp[j]=max(dp[j],dp[j-wp]+vp);
				//看一下是否能拿WP体积的物品I
			//先计算完，再对D进行*2
			d*=2;
		}
	}
	cout<<dp[weight]<<endl;
	
	return 0;
}

习题