파벨은 장난감 기차길이 하나 있다.

기차길은 매우 단순하게 생겼다.

기차길에는 중앙 라인이 한 줄로 있는데, 중앙 라인에는 n개의 기차역이 있으며 기차길 위의 순서 대로 0부터 n−1까지 번호가 붙어 있다.

기차역 i번과 i+1번의 거리는 l_i 센티미터이다 (0 ≤ i < n−1).

중앙 라인 이외에 곁가지들이 있다.

하나의 곁가지는 중앙 라인에 있는 기차역 중 하나에서 시작하여 다른 새로운 (즉, 중앙 라인에 없는) 기차역으로 연결된다.

(새로운 기차역들에는 번호가 없다.)

중앙 라인에 있는 기차역 하나에는 최대 하나의 곁가지가 연결된다.

기차역 i번에 연결된 곁가지의 길이는 d_i로 표현한다.

파벨은 지름길을 하나 만들려고 한다.

지름길은 중앙 라인에 있는 두 개의 기차역을 연결한다.

두 기차역이 이미 인접한 경우에도 지름길을 만들 수 있다.

지름길은 어떤 기차역이 지름길로 연결되는지와 무관하게 그 길이가 정확히 c 센티미터이다.

새로 만든 지름길을 포함해서, 모든 기차길은 양방향으로 통행이 가능하다.

두 기차역 간의 거리는 한 기차역에서 다른 기차역으로 기차길을 이용해서 이동할 수 있는 가장 가까운 길의 길이를 말한다.

전체 기차길의 지름은 모든 쌍의 기차역 간의 거리들 중 최대값이다.

즉, 지름은 어떤 두 기차역 간의 거리도 t보다 작거나 같게 되는 가능한 t 중 가장 작은 것이다.

파벨은 전체 기차길의 지름이 가장 작게 될 수 있도록 지름길을 건설하려고 한다.

Shortcut timer 4s memory 512MB

Shortcut 4s 512MB