void CompletePack(int weight, int value){
	for (int i = weight; i <= half_value; i++){
		dp[i] = max(dp[i], dp[i - weight] + value);
		if (dp[i] == half_value){
			flag = 1;
			return;
		}
	}
	return;
}

void ZeroOnePack(int weight, int value){
	for (int i = half_value; i >= weight; i--){
		dp[i] = max(dp[i], dp[i - weight] + value);
		if (dp[i] == half_value){
			flag = 1;
			return;
		}
	}
	return;
}

void MultiplePack(int weight, int value, int amount){
	if (weight * amount >= half_value){
		CompletePack(weight, value);
		return;
	}
	if (flag) return;
	int k = 1;
	while(k <= amount){
		ZeroOnePack(k * weight, k * value);
		if (flag) return;
		amount -= k;
		k *= 2;
	}
	ZeroOnePack(amount * weight, amount * value);
	return;
}