Railway Diameter Minimization

Pavel has a very simple model railway. The railway contains a main line of n stations numbered consecutively from \(0\) to \(n-1\), with station \(0\) and station \(n-1\) at the two ends. The distance (in centimeters) between station \(i\) and station \(i+1\) is \(l_i\) for \(0 \le i < n-1\).

In addition to the main line, there may be branch lines. Each branch line connects one station on the main line to a new station (which is not numbered) off the main line. At most one branch line can emerge from each main station. The branch line originating from station \(i\) has length \(d_i\) centimeters. A value of \(d_i=0\) indicates that station \(i\) does not have a branch line.

Pavel now plans to build a rapid line: a fast connection between two distinct stations on the main line (they may be adjacent) with a fixed length of \(c\) centimeters. This rapid line, like every other railway, can be used in both directions.

The distance between any two stations in the whole network is defined as the length of the shortest path along the railway tracks (which may combine main line, branch lines, and the rapid line). The diameter of the network is the maximum distance among all pairs of stations. Equivalently, it is the minimum value \(t\) such that the distance between any two stations is at most \(t\).

Your task is to choose two distinct main line stations and connect them with the rapid line (of length \(c\)) so that the resulting railway network has the smallest possible diameter. Output that minimized diameter.

Explanation of Samples

Sample 1

Input:
4 10
10 20 20
0 40 0 30
Optimal: Connect station 1 and station 3. The resulting diameter is 80.
Output:
80

</p>

Sample 2

Input:
9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0
Optimal: Connect station 2 and station 7. The resulting diameter is 110.
Output:
110

</p>

Sample 3

Input:
4 1
2 2 2
1 10 10 1
Optimal: Connect station 1 and station 2. The resulting diameter is 21.
Output:
21

</p>

Sample 4

Input:
3 3
1 1
1 1 1
In this case, any rapid line of length 3 does not improve the network, so the diameter remains 4.
Output:
4

</p>

inputFormat

The first line contains two integers \(n\) and \(c\) where \(n\) is the number of stations on the main line and \(c\) is the fixed length of the rapid line (in centimeters).

The second line contains \(n-1\) integers \(l_0, l_1, \ldots, l_{n-2}\) where \(l_i\) is the distance (in centimeters) between station \(i\) and station \(i+1\).

The third line contains \(n\) integers \(d_0, d_1, \ldots, d_{n-1}\) where \(d_i\) is the length (in centimeters) of the branch line from station \(i\) (with \(d_i = 0\) meaning no branch line exists).

outputFormat

Output a single integer which is the minimized diameter (in centimeters) of the railway network after optimally adding the rapid line.

sample

4 10
10 20 20
0 40 0 30

80