# 直线上的容量运输 预估时间限制：2.5 秒。内存限制：128 MB。 实际时限以标准程序在目标环境的最慢用例中位时间乘以 $18$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。 该倍率为题解中应通过的补充程序保留至少两倍实测余量。 ## 背景故事 走廊上的工作站陆续产出物品。各工作站储位有限，末端仓库容量无限。调度员想知道每个物品前缀的最小搬运距离。 (本故事由GPT-6重写) ## 形式化问题描述 数轴上从左到右有 $n+1$ 个点，编号为 $1,\ldots,n+1$ .点 $i$ 与点 $i+1$ 的距离为 $d_i$ ，可以为零。前 $n$ 个点的容量分别为 $r_1,\ldots,r_n$ ，点 $n+1$ 容量无限。 共有 $m$ 个物品，第 $j$ 个在点 $p_j$ 产生。每个物品必须存放在某个点，允许原地存放；有限容量点存放的物品数不能超过其容量。每个物品的运输费用是产生点到存放点的距离。 对每个 $j=1,\ldots,m$ ，求存放前 $j$ 个物品的最小总费用。各前缀的方案互不影响：优化新的前缀时，可以重新安排此前全部物品的存放位置。 ## 输入格式 第一行两个整数 $n,m$ .第二行给出 $r_1,\ldots,r_n$ ，第三行给出 $d_1,\ldots,d_n$ ，第四行给出 $p_1,\ldots,p_m$ . ## 输出格式 输出 $m$ 行，第 $j$ 行是前 $j$ 个物品的最小总费用。 ## 样例 ### 样例 1 ### 输入 ```text 9 5 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 2 3 5 7 2 9 ``` ### 输出 ```text 1 2 3 3 5 ``` ### 样例 2 ### 输入 ```text 8 4 1 0 1 0 1 0 1 0 2 1 1 1 1 1 1 3 4 6 8 2 ``` ### 输出 ```text 1 2 3 5 ``` ### 样例 3 ### 输入 ```text 2 3 0 1 0 5 1 2 1 ``` ### 输出 ```text 0 5 10 ``` ## 样例解释 样例一的最小费用依次为 $1,2,3,3,5$ .样例二各前缀允许重新安排已有物品。样例三前两个点距离为零，但只有一个有限储位；每增加一个后续物品，都要多付一次距离为五的仓库运输。 ## 数据范围与保证 $1\le n,m\le100000$ ，$0\le r_i\le100000$ .对于 $i