P11142 [APC001] Ex - Separation

小 I 有 $n$ 个工厂，坐落在 $A$ 地到 $B$ 地，第 $i$ 个工厂距离 $A$ 地的距离为 $a_i$ 千米。加工厂位于 $B$ 地，距离 $A$ 地 $x$ 千米，小 I 要把这些工厂里的货物运送到 $B$ 地的加工厂。 但是这天下了暴雨，仓库里的货物受潮了，每份货物每在仓库中或小 I 的背包中存放 $1$ 分钟，价值就会减少 $m$ 元钱。已知今天晚上每个工厂会生产出 $b_i$ 份货物，也知道每份货物会在暴雨来临几分钟后生产出来。 小 I 的初始体力为 $c$，速度为每分钟 $1$ 千米，但是他每行走 $1$ 千米就会减少一点体力（当体力为 $0$ 时不允许行走）。每次出发小 I 都要从 $A$ 地前往 $B$ 地，再返回 $A$ 地，他**只**在从 $A$ 地前往 $B$ 地时会带走沿途的工厂的仓库内所有被生产出的货物。他到达 $A$ 地后可以立刻再次出发。特别的，他可以在**负数时间点**出发，假定他的背包是无限大的，且货物重量与体力消耗无关。 小 I 为了亏损更少，制造了一个分身制造器。这个机器可以制造无数个他的分身，但是每一次出发最多只能制造一个分身，制造的分身与本体共用体力，**完全遵循第 $3$ 段所描述的操作**。小 I 需要保证在任何时候，现有体力都能支持每一个分身（包括本体）返回 $A$ 地的家。 小 I 做完准备工作后，发现暴雨已经下了 $k$ 分钟了，他迫切想要知道他最少要亏损（即货物减少的价值）多少元。他不会这个问题，于是他向你求助，想让你给出一种方案。

无

无

**【样例解释】** 对于样例 $3$ 的第一组数据解释： 小 I 在暴雨来临后 $1$ 分钟向你求助，你给出的方案是在暴雨来临后 $3$ 分钟，小 I 出门，在 $4$ 分钟到达 $1$ 号仓库，在 $5$ 分钟到达 $B$ 地，在 $7$ 分钟回到家，亏损 $3$ 元。 **【数据范围】** 对于全部数据，保证 $1\leq t\leq 10$，$1\leq n\leq 2\times 10^5,1\leq m,k,x\leq 10^6$，$1\le a_i\le x$，$0\leq c\leq 200$，$1\leq b_i\leq 10^5$，$\sum b_i\leq 2\times 10^5$，$0\leq t_{i,j}\leq 10^6$。 **本题输入量较大，请使用较快的读入方式。** 本题题面已更新，[赛时原题面](https://www.luogu.com.cn/paste/iebvx9ko)