Shortcut

Pavel has a toy railway. It is very simple. The railway has one main line of $n$ stations, numbered from 0 to $n-1$ in order along the line. The distance between stations $i$ and $i+1$ is $l_i$ centimeters ($0 \le i \le n-1$).

Apart from the main line, there may be some secondary lines. Each secondary line connects a station on the main line to a new station that is not on the main line. (The new stations are not numbered.) At most one secondary line starts at each station of the main line. The length of the secondary line starting at station $i$ is $d_i$ centimeters. $d_i = 0$ means no secondary line starts at station $i$.

Pavel now plans to build one shortcut: an express line between two different stations (possibly neighbouring ones) of the main line. The express line has length exactly $c$ centimeters, regardless of which two stations it connects.

Each segment of the railway, including the new express line, can be used in both directions. The distance between two stations is the length of the shortest route between them along the railways. The diameter of the network is the maximum distance over all pairs of stations, that is, the smallest $t$ such that the distance between every pair of stations is at most $t$.

Pavel wants to build the express line so that the diameter of the resulting network is minimized.

In all subtasks, $2 \le n \le 1{,}000{,}000$, $1 \le l_i \le 10^9$, $0 \le d_i \le 10^9$, and $1 \le c \le 10^9$.