Shortcut#7977
Pavel has a toy railway. It is very simple. There is a main line consisting of stations. These stations are numbered from to n − 1 in order along the line. The distance between the stations and i + 1 is l_i centimeters (0 \leq i < n − 1).
Apart from the main line there may be some secondary lines. Each secondary line is a railway line between a station on the main line and a new station that does not lie on the main line. (These new stations are not numbered.) At most one secondary line can start in each station of the main line. The length of the secondary line starting at station is d_i centimeters. We use d_i = 0 to denote that there is no secondary line starting at station .
Pavel is now planning to build one shortcut: an express line between two different (possibly neighboring) stations of the main line. Express line will have length of exactly centimeters, regardless of what two stations it will connect.
Each segment of the railway, including the new express line, can be used in both directions. The distance between two stations is the smallest length of a route that goes from one station to the other along the railways. The diameter of the whole railway network is the maximum distance among all pairs of stations. In other words, this is the smallest number , such that the distance between every pair of stations is at most .
Pavel wants to build the express line in such a way that the diameter of the resulting network is minimized.
First line contains integers and (2 \leq n \leq 10^6, 1 \leq c \leq 10^9).
Second line contains integers l_0, \ldots, l_{n-2} (1 \leq l_i \leq 10^9).
Third line contains integers d_0, \ldots, d_{n-1} (0 \leq d_i \leq 10^9).
Print a single integer denoting the smallest possible diameter.
Example 1
Example 2
Example 3
Example 4
The optimal solution is to build the express line between stations and , as shown below.
