P7747 [COCI 2011/2012 #3] TRAKA

Mirko 的工厂里面有 $n$ 个工人。他们以流水线方式在传送带上制造汽车。工人从左往右编号为 $1\sim n$，其中工人 $1$ 即为 Mirko。汽车生产从工人 $1$（Mirko）开始，在他完成所有他的工作后，工人 $2$ 接手他的任务。之后工人 $3$ 再接手工人 $2$ 的任务，以此类推。当工人 $n$ 完成他的工作后，一辆汽车就生产完成了。 Mirko 和他的工人们必须生产 $m$ 辆汽车，且必须按 $1\sim m$ 的顺序生产。对于第 $i$ 个工人，他完成他的工作的时间为 $t_i$。对于第 $j$ 辆汽车，它装配的复杂度为 $f_j$。工人 $i$ 在汽车 $j$ 上完成他的工作所需时间为 $t_i\cdot f_j$。 根据公司政策，一个工人完成他的工作后，他必须立即将工作交给下一个工人，不得拖延。因此，下一个工人此时不能够在其他汽车上工作。为了满足这个条件，Mirko 必须等到一个好的时机开始制造一辆新车。为了提高效率，他将等待最少的时间，直到他确定能够满足所有条件。 编写一个程序，给定每个工人完成他的工作的时间和每辆车装配的复杂度，求生产所有汽车所需的总时间。

输入共 $n+m+2$ 行。 第一行，两个整数 $n,m$，分别代表工人的个数和需要生产的汽车的辆数。 随后 $n$ 行，每行一个整数 $t_i$，表示第 $i$ 个工人完成他的工作的时间。 随后 $m$ 行，每行一个整数 $f_j$，表示第 $j$ 辆车装配的复杂度。

输出仅一行一个整数，表示生产所有汽车所需的总时间。

**【样例 1 解释】** 对于样例 $1$，$4$ 个单位的时间后，工人 $1$ 完成了第一辆车的工作。他可能会立即开始在第二辆车上工作，但这违反了汽车必须在完成后立即传递给下一个工人的条件（$7$ 个单位的时间后第二个工人将完成他在第二辆车上的工作，但是第三个工人不能接手，因为他仍然在第一辆车上工作）。因此，第二辆车在 $5$ 个单位的时间后才能开始生产。$7$ 个单位的时间后开始生产第三辆汽车。第一辆车在 $8$ 个单位的时间后完成，第二辆车在 $9$ 个单位的时间后完成，第三辆车在 $11$ 个单位的时间后完成。因此总时间是 $11$。 **【数据范围】** 对于 $40\%$ 的数据，满足 $n,m\leqslant 1000$。 对于所有数据，$1\leqslant n,m\leqslant 10^5$，$1\leqslant t_i,f_j\leqslant 10^4$。 **【题目来源】** 本题来源自 **_[COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST 3](https://hsin.hr/coci/archive/2011_2012/contest3_tasks.pdf) T6 TRAKA_**，按照原题数据配置，满分 $160$ 分。 由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。