题目类型说明

这是一道提交函数题。你需要提交 stations.cpp，实现指定函数，不需要编写 main 函数。

你需要实现：

long long init(int L, int K, int N, int stationPositions[], int stationOilPrices[]);
long long addStation(int newStationPosition, int newStationOilPrice);

---

题目描述

夏天快到了，Laura 每天都梦想着去海边过无忧无虑的日子。由于她不太想工作，她整天都在规划去海边的旅行。可是不工作毕竟赚不到什么钱，所以她希望把旅行费用尽量压到最低。

为简单起见，假设 Laura 要走的道路位于一条数轴上，总长度为 L，起点在 0，终点在 L。Laura 的汽车有一个容量为 K 升的油箱，且最开始是空的。路上有 N 个加油站，位置各不相同。编号为 i 的加油站位于整数坐标 Xi，在那里可以以每升 Ci 的价格加油。

Laura 行驶长度为 1 的路程，恰好消耗 1 升油。如果某一时刻她恰好在某个加油站所在位置，那么她可以一次加任意整数升的油，但不能超过油箱容量。

现在 Laura 希望你写一个程序，帮她规划每次在什么地方加多少油，从而用最低花费到达海边。可惜现在离夏天还早，到那时可能会发生很多变化。因此你的程序还需要处理 Q 次询问，每次询问表示在道路上的某个新位置开设一个新的加油站。保证任意时刻 Laura 都存在一种方案可以走完长度为 L 的路程，并且任意时刻都不会有两个加油站位于同一位置。

程序需要在初始加油站集合下，以及每次新增加油站之后，都计算出 Laura 到达海边的最小可能花费。

---

任务

请编写函数 init() 和 addStation()，它们会与评测程序一起编译。它们在得到初始加油站集合的信息，以及每个新加油站的信息后，需要分别返回 Laura 在当前加油站集合下到达海边的最小花费。

---

实现细节

你需要提交源文件 stations.cpp，其中包含以下函数：

long long init(int L, int K, int N, int stationPositions[], int stationOilPrices[]);
long long addStation(int newStationPosition, int newStationOilPrice);

init

init 只会在程序开始时被调用一次，其参数含义如下：

• L：到海边道路的总长度；
• K：Laura 汽车油箱的容量（升）；
• N：初始加油站集合中的加油站数量；
• stationPositions：初始加油站坐标数组，下标从 0 开始；
• stationOilPrices：初始加油站的油价数组，下标从 0 开始。

init 需要返回：在初始加油站集合下，Laura 到达海边所需的最小花费。

注意： 初始加油站不保证按坐标升序给出。

addStation

addStation 会被调用 Q 次，每次对应一次新建加油站的询问。其参数含义如下：

• newStationPosition：新加油站的位置；
• newStationOilPrice：新加油站的每升油价。

每次调用 addStation 时，你都需要返回：加入这个新加油站之后，Laura 到达海边所需的最小花费。

其他要求

• 文件 stations.cpp 不能包含 main() 函数；
• 但可以包含实现 init 和 addStation 所需的其他声明与辅助函数；
• 文件开头必须包含：

#include "stations.h"

---

限制

• 0 ≤ Ci ≤ 10^9
• 0 ≤ Xi ≤ L

保证任意时刻都存在解。

---

子任务

题目分为若干子任务。要获得某个子任务的分数，必须通过该子任务中的所有测试。

子任务	分值	N 范围	Q 范围	L, K 范围
1	10	1 ≤ N ≤ 100	1 ≤ Q ≤ 100	1 ≤ L, K ≤ 100
2	11	1 ≤ N ≤ 1000		1 ≤ L, K ≤ 10^9
3	16	1 ≤ N ≤ 2000	1 ≤ Q ≤ 2000
4	12	1 ≤ N ≤ 5000	1 ≤ Q ≤ 5000
5	23	1 ≤ N ≤ 80000	1 ≤ Q ≤ 80000
6	28	1 ≤ N ≤ 300000	1 ≤ Q ≤ 300000

---

示例

被调用函数	L	K	N	stationPositions / newStationPosition	stationOilPrices / newStationOilPrice	返回值
init	100	42	5	82 0 35 68 40	216 210 215 220 212	21188
addStation				90	209	21118

示例说明

在由 init 给定的初始加油站布局下，对 Laura 最优的加油方案是：

• 在位置 0 的加油站加 42 升；
• 在位置 40 的加油站加 40 升；
• 在位置 82 的加油站加 18 升。

加入位置 90、油价更低的新加油站之后，更优的方案变成：

• 在位置 0 的加油站加 42 升；
• 在位置 40 的加油站加 40 升；
• 在位置 82 的加油站加 8 升；
• 在位置 90 的加油站加 10 升。

---

本地测试

为了在本地测试你的 init() 与 addStation()，题目提供了文件 Lgrader.cpp 和 stations.h。将它们与 stations.cpp 一起编译，就能得到用于本地测试的程序。

本地测试程序从标准输入读取如下数据：

• 第一行：三个正整数 L, K, N，分别表示道路总长度、油箱容量、初始加油站数；
• 第二行：N 个非负整数，表示初始加油站的位置；
• 第三行：N 个非负整数，表示初始加油站的油价；
• 下一行：一个非负整数 Q，表示新增加油站的询问数；
• 接下来 Q 行：每行两个非负整数，表示一个新加油站的位置和该站的每升油价。

程序输出 Q+1 行，每行一个整数，依次表示：

• 初始加油站集合下的最小花费；
• 每次加入新加油站之后的最小花费。