说明

布迪偶然发现了他在大学课堂上学过的经典 0-1 背包问题。有 $N$ 个物品，编号从 $1$ 到 $N$。第 $i$ 个物品有一个正整数重量 $W_i$ 和一个正整数价值 $V_i$。目标是在总重量不超过 $M$ 的前提下，选择零个或多个物品，使得总价值最大。

布迪已经很久没有研究这个问题了，他想不起如何解决它。于是，布迪设计了一个贪心算法来尝试解决这个问题。算法如下：按照从第 $1$ 个物品到第 $N$ 个物品的顺序依次处理每个物品。如果当前物品可以被选取，且加入后总重量不超过 $M$，则选取该物品；否则，忽略它。最后输出所有选取物品的总价值。

该贪心算法可以用以下伪代码表示：

GreedyKnapsack(W[1..N], V[1..N], M):
    total_value = 0
    total_weight = 0
    for i = 1 to N:
        if total_weight + W[i] <= M:
            total_weight = total_weight + W[i]
            total_value = total_value + V[i]
    return total_value

当然，布迪意识到这种贪心算法可能无法得到最优解，但此刻他并不在意。布迪注意到该贪心算法的输出对参数 $M$ 很敏感。因此，他决定让 $M$ 从 $1$ 到给定的上限 $T$ 变化，运行该贪心算法，并找出他能得到的最大输出值。

你的任务是帮助布迪确定，通过让输入参数 $M$ 从 $1$ 变化到 $T$，他能从该贪心算法中获得的最大输出值。

例如，设 $N = 5$，$T = 10$，$W_{1..5} = \{10, 1, 2, 3, 4\}$，$V_{1..5} = \{1, 1, 1, 1, 1\}$。在此例中，能获得的最大输出为 $3$，例如取 $M = 6$ 时，贪心算法会选取第 $2$、$3$、$4$ 个物品，总重量为 $1 + 2 + 3 = 6$，总价值为 $1 + 1 + 1 = 3$。注意，如果设 $M = 10$，则贪心算法只会选取第 $1$ 个物品，总重量为 $10$，总价值为 $1$。

输入格式

输入第一行包含两个整数 $N$ 和 $T$（$1 \leq N \leq 100\,000$；$1 \leq T \leq 10^{10}$），分别表示物品数量和价值上限。第二行包含 $N$ 个整数 $W_i$（$1 \leq W_i \leq 100\,000$），表示第 $i$ 个物品的重量。第三行包含 $N$ 个整数 $V_i$（$1 \leq V_i \leq 100\,000$），表示第 $i$ 个物品的价值。

输出格式

输出一行一个整数，表示通过所述贪心算法能获得的最大输出值。

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

3

5 10000000000
10 1 2 3 4
30 2 15 7 11

65

5 20
4 9 5 1 3
203 175 131 218 304

900

提示

样例 #2 解释

你可以将 $M$ 设得足够大，使得所有物品都能被选取，即 $M \geq 20$。

样例 #3 解释

取 $M = 17$ 可获得最大输出。此时第 $1$、$2$、$4$、$5$ 个物品会被选取，总重量为 $4 + 9 + 1 + 3 = 17$，总价值为 $203 + 175 + 218 + 304 = 900$。

翻译由 DeepSeek 完成