题目描述

Pavel 有一个非常简单的铁路玩具。 它有一条含有 $n$ 个车站的主干线并且连续编号为 $0$ 到 $n-1$。车站 $0$ 和车站 $n-1$ 就在这条主干线的两端。其中车站 $i$ 和车站 $i+1$ 之间的距离为 $l_i$ 厘米（$0 \le i<n-1$）。

除了这条主干线之外，这个铁路也许会有些支线。每条支线都是由主干线中的一个车站和主干线 外的一个新车站之间的一条新铁路构成（这些新的车站不会被编号）。在主干线中的一个车站最多只能有一条支线。以主干线中的车站 $i$ 为起点的支线的长度为 $d_i$ 厘米。我们用 $d_i=0$ 来表示车站 $i$ 没有支线。

Pavel 现正规划一条快捷方式：一条在主干线中两个不相同的车站之间（它们可能相邻）的快速干线。这条快速干线无论是连接哪两个车站，它的长度都将会恰好是 $c$ 厘米。

铁路中的每一段，包括那条新的快速干线，都能够双向行驶。任意两个车站的距离就是它们之间沿着铁路由一个车站到另一个车站之间最短路径的长度。所有车站组合中最大的距离就叫做整个铁路网络的直径。换句话说，存在一个最小值 $t$ 使任意两个车站之间的距离都不会超过 $t$。

Pavel 就是想建造一条快速干线，使得有了这条快速干线后新的铁路网络的直径能达到最小值。

样例一

4 10
10 20 20
0 40 0 30

最优解是在车站 $1$ 和车站 $3$ 之间建造一条快速干线，如下图所示。

这个新铁路网络的直径是 $80$ 厘米，所以应该输出数值 $80$。

样例二

9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0

最优解是连接车站 $2$ 和车站 $7$，这个解的直径是 $110$。

样例三

4 1
2 2 2
1 10 10 1

最优解是连接车站 $1$ 和车站 $2$，这样直径将被缩短到 $21$。

样例四

3 3
1 1 
1 1 1

在任意两个车站中建立长度为 $3$ 的快速干线都不会改进整个铁路网络的直径，因此其直径仍为初始值 $4$。

输入格式

• 第一行：两个整数 $n$ 和 $c$，

• 第二行：整数 $l_0,l_1,\cdots,l_{n-2}$，

• 第三行：整数 $d_0,d_1,\cdots,d_{n-1}$。

输出格式

共一行，加入新快速干线后铁路网络直径的最小可能值。

4 10
10 20 20
0 40 0 30

80

提示

对于 $100\%$ 的数据，$2\le n\le 10^6$，$1\le l_i\le 10^9$，$0\le d_i\le 10^9$，$1\le c\le 10^9$。