题解

题面描述

有一个 $n$ 层的珠宝塔，每一层都有无限数量的一种珠宝。第 $i$ 层的珠宝需要花费 $i$ 个金币购买，而每个珠宝的价值为 $a_i$ 。每当你第一次进入第 $i$ 层时，会获得 $k_i$ 个金币作为奖励。
从第 $1$ 层开始向上，每层到达后你都有两种选择：

• ALLIN：花光当前所有金币购买该层珠宝。由于没有找零机制，即使你手中的金币数不能被 $i$ 整除，也只能购买 $\lfloor \frac{x}{i} \rfloor$ 个珠宝，从而获得价值 $\lfloor \frac{x}{i} \rfloor \times a_i$ ，此时金币清零，然后进入第 $i+1$ 层。
• SKIP：不进行购买，直接进入第 $i+1$ 层（若在第 $n$ 层则直接离开）。

题目内容

有一个 $n$ 层的珠宝塔，每一层都有一种珠宝数量无限。具体地，第 $i$ 层的珠宝价格为 $i$ 个金币价值为 $a_i$ 。

现在，您将从第 $1$ 层开始，逐层向上攀登。每当你第一次进入第 $i$ 层时，你将会得到 $k_i$ 个金币的初始奖励，而后你有两种选择：

• $ALLIN$ ：花光所有金币，购买当前层的珠宝，并且，由于不设找零，所以多花的钱会直接消失(即假如你有 $x$ 个金币，你将得到 $\frac{x}{i}×a_i$ 的价值，并且你手中金币数将变为 $0$ )；随后进入第 $i+1$ 层；

• $SKIP$ ：直接进入第 $i+1$ 层，如果此时你位于第 $n$ 层你将会直接离开珠宝塔。

初始时你有 $y$ 个金币，请问，从第 $1$ 层进入到第 $n$ 层最终离开，你最多能获得多少价值？

输入描述

第一行输入两个整数

$n,y(1≦n≦5×10^3;0≦y≦10^5)$ 代表珠宝塔的层、你初始拥有的金币数量。

第二行输入 $n$ 个整数 $k_i,k_2,...,k_n(1 ≦k_i≦ 10^5)$ 代表进入第 $i$ 层你将得到的金币数量。

第三行输入 $n$ 个整数

$a_1,a_2,…,a_n(1≦a_i≤10^5)$ 代表第 $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$ 的珠宝。