CF1809F Traveling in Berland

在 Berland 有 $n$ 个城市，这些城市按顺时针顺序排列成一个环，编号为 $1$ 到 $n$。 你想要环游整个 Berland，从某个城市出发，访问所有其他城市，并最终回到起点。不幸的是，你只能沿着 Berland 环形公路行驶，这条公路连接了所有 $n$ 个城市。由于这条路是由一位非常有头衔且受人尊敬的部长设计的，所以它是单向的——只能顺时针行驶，只能从第 $i$ 个城市到第 $(i \bmod n) + 1$ 个城市（即从 $1$ 到 $2$，从 $2$ 到 $3$，……，从 $n$ 到 $1$）。 你的汽车油箱最多能装 $k$ 升油。从第 $i$ 个城市到下一个城市需要消耗 $a_i$ 升油（并在途中消耗掉）。 每个城市都有加油站；在第 $i$ 个城市每升油的价格为 $b_i$ burles。禁止在城市之间加油；如果在城市之间油用完了，你的旅程就算失败。 对于每个城市，计算如果从该城市出发并最终回到该城市，完成整个旅程的最小花费。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$3 \le n \le 2 \cdot 10^5$；$1 \le k \le 10^9$），分别表示城市数量和油箱容量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le k$）。 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le 2$）。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出 $n$ 个整数，第 $i$ 个整数表示如果从第 $i$ 个城市出发并最终回到该城市，完成整个旅程的最小花费。

由 ChatGPT 4.1 翻译