思路:动态规划-完全背包

对于每种水晶，激活需要消耗法力，同时需要购买祭品、卖出水晶，净收益为售价减去祭品价格。同一种水晶可以重复激活。这是一个完全背包问题。总法力上限 $m$ 就是背包容量，单块水晶消耗的法力 $c_i$ 就是物品体积，净收益 $s_i - p_i$ 就是物品的价值。

知识点学习:动态规划

1.动态规划(dp)入门 by 一只会code的小金鱼

推荐理由:由浅入深,从dfs -> 记忆化搜索 -> 动态规划 的思路来讲解dp。也是公认的比较符合人类思维的理解dp的过程。

题目内容

探险家小蓝在远古遗迹中发现了一座密室，密室内有 $n$ 种蕴含魔力的能量水晶。小蓝携带的魔法石拥有总量为 $m$ 的法力。激活一块水晶需要消耗固定的法力，并需要购买特制祭品作为媒介；激活后的水晶可以立刻卖给古物商人换取金币。由于祭品可以随时购买且初始资金充足，小蓝唯一受限的是魔法石的总法力。

对于第 $i$ 种水晶，激活一次需要消耗 $c_i$ 点法力，购买祭品需花费 $p_i$ 枚金币，卖出水晶可获得 $s_i$ 枚金币。每次激活必须一次性完成，无法中断。同一种水晶可以重复激活，只要剩余法力足够。每激活一块水晶的净收益为 $s_i - p_i$。小蓝想通过若干次激活，在总法力消耗不超过 $m$ 的前提下，使总净收益最大化。

请你计算出小蓝最多能赚取的金币数量。

约束条件：

• 水晶种类数 $n$ 和总法力 $m$ 满足 $1 \le n, m \le 1000$。
• 每种水晶的法力消耗 $c_i$ 满足 $1 \le c_i \le m$。
• 祭品价格 $p_i$ 和售价 $s_i$ 均为正整数，满足 $1 \le p_i \le s_i \le 10^5$。

输入描述

第一行包含两个整数 $n$ 和 $m$，分别表示水晶种类数和魔法石总法力值。 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$，表示每种水晶激活所需的法力消耗。 第三行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示每种水晶所需祭品的价格。 第四行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$，表示每种水晶的售价。

输出描述

输出一个整数，表示小蓝最多能赚取的金币数量。

样例1

输入

1 10
5
2
7

输出

10

说明

只有一种水晶，其法力消耗为 $c_1 = 5$，祭品价格 $p_1 = 2$，售价 $s_1 = 7$。单次激活的净收益为 $s_1 - p_1 = 5$ 金币。

魔法石总法力为 $m = 10$，可以激活 $\lfloor 10 / 5 \rfloor = 2$ 次。总净收益为 $2 imes 5 = 10$ 金币。所以最多赚取 10 金币。

样例2

输入

2 9
4 5
1 2
3 7

输出

7

说明

有两种水晶。 第一种：法力消耗 $c_1 = 4$，祭品价格 $p_1 = 1$，售价 $s_1 = 3$，净收益 $w_1 = 2$。 第二种：法力消耗 $c_2 = 5$，祭品价格 $p_2 = 2$，售价 $s_2 = 7$，净收益 $w_2 = 5$。

总法力 $m = 9$。可以选择激活第一种水晶一次（消耗 $4$ 法力，收益 $2$）和第二种水晶一次（消耗 $5$ 法力，收益 $5$），总法力消耗 $4 + 5 = 9$，总收益 $2 + 5 = 7$。其他方案（如激活两次第一种，消耗 $8$ 法力收益 $4$；仅激活一次第二种，收益 $5$）均无法得到更高收益。因此最多赚取 7 金币。

样例3

输入

1 1000
1000
500
1500

输出

1000

说明

只有一种水晶，法力消耗 $c_1 = 1000$，祭品价格 $p_1 = 500$，售价 $s_1 = 1500$。单次净收益 $1500 - 500 = 1000$ 金币。

魔法石总法力 $m = 1000$ 恰好等于一次激活的消耗，因此只能激活 $1$ 次，收益为 $1000$ 金币。这是法力刚好用完的边界情况。