题解
题面描述
有一个 n 层的珠宝塔，每一层都有无限数量的一种珠宝。第 i 层的珠宝需要花费 i 个金币购买，而每个珠宝的价值为 ai 。每当你第一次进入第 i 层时，会获得 ki 个金币作为奖励。
从第 1 层开始向上，每层到达后你都有两种选择：
- ALLIN：花光当前所有金币购买该层珠宝。由于没有找零机制，即使你手中的金币数不能被 i 整除，也只能购买 ⌊ix⌋ 个珠宝，从而获得价值 ⌊ix⌋×ai ，此时金币清零，然后进入第 i+1 层。
- SKIP：不进行购买，直接进入第 i+1 层（若在第 n 层则直接离开）。
P2837.第3题-珠宝塔
题目内容
有一个 n 层的珠宝塔，每一层都有一种珠宝数量无限。具体地，第 i 层的珠宝价格为 i 个金币价值为 ai 。
现在，您将从第 1 层开始，逐层向上攀登。每当你第一次进入第 i 层时，你将会得到 ki 个金币的初始奖励，而后你有两种选择：
初始时你有 y 个金币，请问，从第 1 层进入到第 n 层最终离开，你最多能获得多少价值？
输入描述
第一行输入两个整数
n,y(1≦n≦5×103;0≦y≦105) 代表珠宝塔的层、你初始拥有的金币数量。
第二行输入 n 个整数 ki,k2,...,kn(1≦ki≦105) 代表进入第 i 层你将得到的金币数量。
第三行输入 n 个整数
a1,a2,…,an(1≦ai≤105) 代表第 i 层珠宝的价值。
输出描述
输出一个整数代表你能得到的最大价值。
样例1
输入
3 0
1 1 1
1 3 1
输出
3
说明
在这个样例中，最优的购买方案为：
-
第一层直接 SKIP ，此时拥有 1 个金币；
-
第二层 ALLIN ，花费 2 个金币购买珠宝，得到 3 价值的珠宝，随后进入第三层；
-
第三层直接 SKIP ，此时拥有 1 个金币。
样例2
输入
5 2
1 2 3 4 4
2 1 3 1 4
输出
15
说明
在这个样例中，最优的购买方案为：
-
进入第一层时，一共拥有 3 个金币，直接 ALLIN ，得到 6 价值的珠宝；
-
进入第二层时，一共拥有 2 个金币，直接 ALLIN ，得到 1 价值的珠宝；
-
进入第三层时，一共拥有 3 个金币，SKIP ;
-
进入第四层时，一共拥有 7 个金币，SKIP ;
-
进入第五层时，一共拥有 11 个金币，直接 ALLIN ，得到 8 价值的珠宝。
最终，一共获得价值为 6+1+8=15 的珠宝。
