解题思路

把整段路抽象为：行驶段 $c_1,\dots,c_n$ 与中间等待段 $t_1,\dots,t_{n-1}$。 一次连续乘坐时长为 $L$ 的费用函数为

关键：等待段可以选择“在车上”(把相邻行驶段合并成一个更长的连续乘坐)或“下车”(不计费并切断一次乘坐)。因此问题变成：在每个等待点处，决定“合并”还是“断开”，使 $\sum f(\text{每次连续乘坐长度})$ 最小。

题目内容

小明去了另一个城市旅游。他打算坐出租车到下一个景点。

众所周知，出租车有起步价和单价。但是这个城市的出租车却有些特殊，是以分钟为单位计价。

在某一个给定的时间内，只需要付起步价;用时超过该时间后，每分钟需额外付单价。

具体的，设起步价为 $a$ 元，单价为 $b$ 元，给定的时间为 $s$ 分钟，则总价钱 $y$ 与分钟数 $x$ 可以用以下的函数关系式表示:

$\mathrm{y}=\left\{\begin{array}{c}a, x \leq s \\a+b \cdot(x-s), x>s\end{array}\right. $

不幸的是，小明当前的位置与目的地之间有很多的红绿灯，因此出租车行驶一会儿就必须停下来等红绿灯。

现在小明算出了每段路出租车会行驶的时间以及停留的时间。

假设小明可以随时随地下出租车，并且一下出租车就能立马打到另一辆出租车。

请帮助小明规划打车的方案，使他所需付的钱最少。

输入描述

第一行三个整数 $a,b,s(1≤a,b,s≤10^5,a> b•s)$ ,表示出租车的起步价，单价，以及起步价对应的分钟数。

第二行一个整数 $n(2≤n≤10^6)$ ，表示从小明所处的位置到景点共有 $n$ 段路。

第三行 $n$ 个整数，其中第 $i$ 个整数 $c_i(s≤c_i≤10^5)$ 表示第 $i$ 段路的用时，单位为分钟。

第四行 $n-1$ 个整数，其中第 $i$ 个整数 $t(1≤t≤10^5)$ 表示第 $i$ 段路与第 $i+1$ 段路之间需要等待的时间，单位为分钟。

输出描述

一行，一个整数，表示所需付的钱的最小值。

样例1

输入

7 1 5
4
6 7 5 8
1 11 1

输出

32

说明

一种可行的方案为:在第一段路打车，第二段路结束时下车;在第三段路重新打车，一直坐到目的地。总花费为 $[7+1*(6+1+7-5)]+[7+1*(5+1+8-5)]=32$ 元，可以证明此为最小花费。