Polycarp车上的车载计算机测量到,在路径的某些路段开始处的车速为每秒v1米,最后为每秒v2米。我们知道这段路线正好花了 t 秒才通过。
假设每一秒的速度是恒定的,并且秒之间速度的绝对值最多可以改变 d 米每秒(即任何相邻两秒的速度差的绝对值不超过 d),求路径段的最大可能长度(以米为单位)。
输入
第一行包含两个整数 v1 和 v2 (1 ≤ v1, v2 ≤ 100) — 分别是段开始处和段结束处的速度(以米每秒为单位)。
第二行包含两个整数 t (2 ≤ t ≤ 100) — 汽车沿路段移动的时间(以秒为单位),d (0 ≤ d ≤ 10) — 相邻秒之间速度变化的最大值。
保证有一种方法可以完成该段,以便:
- 第一秒的速度等于v1,
- 最后一秒的速度等于v2,
- 任意两相邻秒之间的速度差的绝对值不超过 d。
输出
打印路径段的最大可能长度(以米为单位)。
示例
输入 #1
5 6 4 2
输出 #1
26
输入 #2
10 10 10 0
输出 #2
100
注意
在第一个示例中,Polycarpus 的汽车的速度顺序如下:5、7、8、6。因此,总路径为 5 + 7 + 8 + 6 = 26 米。
在第二个示例中,当 d = 0 时,汽车以恒定速度 v = 10 行驶整个路段。在 t = 10 秒内,它行驶了 100 米的距离。