지름길

파벨은 장난감 철도를 가지고 있다. 철도는 매우 단순하다. 본선은 하나이며, $n$개의 역으로 이루어진다. 역은 선을 따라 0부터 $n-1$까지 순서대로 번호가 매겨져 있다. 역 $i$와 역 $i+1$ 사이의 거리는 $l_i$ 센티미터이다 ($0 \le i \le n-1$).

본선 외에 보조선이 여러 개 있을 수 있다. 각 보조선은 본선의 역 하나와 본선에 속하지 않는 새 역 하나를 잇는다. (새 역에는 번호가 없다.) 본선의 각 역에서는 보조선이 최대 하나만 시작한다. 역 $i$에서 시작하는 보조선의 길이는 $d_i$ 센티미터이다. $d_i = 0$이면 역 $i$에서 시작하는 보조선이 없다는 뜻이다.

파벨은 지금 지름길 하나를 건설하려고 한다. 지름길은 본선에 있는 서로 다른 두 역(서로 이웃해도 된다)을 잇는 급행선이다. 급행선의 길이는 어떤 두 역을 잇든 정확히 $c$ 센티미터이다.

급행선을 포함한 모든 철도 구간은 양방향으로 이용할 수 있다. 두 역 사이의 거리는 철도를 따라 갈 수 있는 경로 중 가장 짧은 길이이다. 철도망의 지름은 모든 역 쌍 사이 거리의 최댓값이다. 즉, 모든 역 쌍의 거리가 $t$ 이하가 되도록 하는 가장 작은 $t$가 지름이다.

파벨은 철도망의 지름이 최소가 되도록 급행선을 건설하려고 한다.

모든 서브태스크에서 $2 \le n \le 1{,}000{,}000$, $1 \le l_i \le 10^9$, $0 \le d_i \le 10^9$, $1 \le c \le 10^9$이다.