P15609 [ICPC 2021 Jakarta R] Greedy Knapsack

布迪偶然发现了他在大学课堂上学过的经典 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]

输入第一行包含两个整数 $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$ 个物品的价值。

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

#### 样例 #2 解释 你可以将 $M$ 设得足够大，使得所有物品都能被选取，即 $M \geq 20$。 #### 样例 #3 解释 取 $M = 17$ 可获得最大输出。此时第 $1$、$2$、$4$、$5$ 个物品会被选取，总重量为 $4 + 9 + 1 + 3 = 17$，总价值为 $203 + 175 + 218 + 304 = 900$。 翻译由 DeepSeek 完成