问题描述

有一个 $n$ 层的墓穴，每层墓穴珠宝无限供应。第 $i$ 层的珠宝价格为 $i$ 个金币，价值为 $a_i$。从第 $1$ 层开始逐层向上攀登，第一次进入第 $i$ 层时会获得 $k_i$ 个金币的初始奖励，然后有两种选择：

1. COST：花光所有金币购买当前层珠宝，获得 $\left\lfloor \frac{x}{i} \right\rfloor \times a_i$ 价值（$x$ 为当前金币），金币归零，进入 $i+1$ 层
2. JUMP：直接进入 $i+1$ 层（如果是第 $n$ 层则离开）

初始有 $y$ 个金币，求从第 $1$ 层到第 $n$ 层能获得的最大价值。

输入格式

• 第一行：$n$, $y$ 。
• 第二行：$k_1$, $k_2$, ..., $k_n$。
• 第三行：$a_1$, $a_2$, ..., $a_n$ 。

输出格式

最大可获得价值。

样例输入

3 0
1 1 1
1 3 1

样例输出

3

样例输入

5 2
1 2 3 4 4
2 1 3 1 4

样例输出

15

数据范围

• 对于前 $20\%$ 的数据：$1 \leq n \leq 10$.
• 对于前 $40\%$ 的数据：$1 \leq n \leq 200$ , $0 \leq y \leq 10^3$ , $1 \leq k_i,a_i \leq 10^3$.
• 对于 $100\%$ 的数据：$1 \leq n \leq 5*10^3$ ，$0 \leq y \leq 10^5$ , $1 \leq k_i,a_i \leq 10^5$