P4480 [BJWC2018] 餐巾计划问题

**本题和网络流24题中的餐巾计划不为重题**

一个餐厅在相继的 $n$ 天里，每天需用的餐巾数不尽相同。假设第 $i$ 天 $(i=1, 2, ..., n)$ 需要 $r_i$ 块餐巾。餐厅可以在任意时刻购买新的餐巾，每块餐巾的费用为 $p$ 。使用过的旧餐巾，则需要经过清洗才能重新使用。把一块旧餐巾送到清洗店A，需要等待 $m_1$ 天后才能拿到新餐巾，其费用为 $c_1$ ；把一块旧餐巾送到清洗店B，需要等待 $m_2$ 天后才能拿到新餐巾，其费用为 $c_2$ 。例如，将一块第 $k$ 天使用过的餐巾送到清洗店A清洗，则可以在第 $k+m_1$ 天使用。 请为餐厅合理地安排好 $n$ 天中餐巾使用计划，使总的花费最小。

无

无

**【样例说明】** 第 1 天：买8块餐巾，花费24。送2块餐巾去清洗店A，6块餐巾去清洗店B。 第 2 天：取回2块清洗店A的餐巾，花费4。送1块餐巾去清洗店B。 第 3 天：取回6块清洗店B的餐巾，花费6。 第 4 天：取回1块清洗店B的餐巾，花费1。这样就用了最少的钱。 **【数据规模和约定】** 对于30%的数据，$1 \leq n \leq 5$ ，$1 \leq c_1, c_2, p \leq 5$ ， $1 \leq r_i \leq 5$ 。 对于50%的数据，$1 \leq n \leq 100$ ，$1 \leq r_i \leq 50$ 。 对于70%的数据，$1 \leq n \leq 5000$ 。 对于100%的数据，$1 \leq n \leq 200000$ ， $1 \leq m_1, m_2 \leq n$ ， $1 \leq c_1, c_2, p \leq 100$ ， $1 \leq r_i \leq 100$ 。