해돋이

준이는 내일 중간고사가 있는데 아무것도 공부하지 않았다. 그래서 밤을 새워 공부하기로 했다. 준이는 해가 뜨기 전에는 공부를 멈추지 않겠다고 다짐했다.

준이의 집은 어떤 산속에 있다. 편의상 준이는 2차원 좌표계에 살고 있다고 하자. 산은 $y\geq 0$ 영역에 있고 $x=a_0$에서 시작하며, 그 경계는 $y=x$ 또는 $y=-x$와 평행한 $2n$개의 선분으로 이루어진다.

더 정확히 말하면, 산의 경계는 $(2n-1)$개의 정수로 나타낼 수 있는데, 그중 $i$번째 수 $a_i$는 산의 $i$번째 뾰족점의 $x$좌표이다. 경계선은 $(a_0,\ 0)$에서 시작하여 $x$좌표가 $a_1$에 도달할 때까지 $y=x$와 평행하게 진행하고, 그다음 $x$좌표가 $a_2$에 도달할 때까지 $y=-x$와 평행하게 진행하는 식으로 이어진다. 마지막 단계가 끝나면 $x$축과 만날 때까지 $y=-x$와 평행하게 진행한다.

산의 내부는 경계 아래, $x$축 위의 영역이다. 따라서 내부와 경계는 서로 겹치지 않는다.

$x=a_0$와 $x=a_{2n-1}$ 사이의 어느 지점에서, 산의 경계 위에 준이의 집이 있다. 집의 크기는 산에 비해 무시할 수 있을 만큼 작다.

현재 태양은 원점에 있고 분당 1의 속도로 수직으로($+y$ 방향으로) 떠오른다. 준이는 집과 태양을 잇는 선분이 산의 내부와 교차하지 않으면 태양을 볼 수 있다. 준이는 완전히 지쳐서 언제 공부를 멈출 수 있는지 알고 싶어 한다. 하지만 짐작하겠지만 준은 정신이 없어서 그런 어려운 계산을 할 수 없다. 준을 도와주자!

첫 번째 줄에 정수 $n$이 주어진다 ($1\leq n\leq 1,000$).

다음 줄에 $2n$개의 정수가 주어지며, $i$번째 정수는 $a_{i-1}$이다 ($1\leq a_0<\cdots<a_{2n-1}\leq 10^6$).

마지막 줄에 준의 집의 $x$좌표인 정수 $x$가 주어진다 ($a_0\leq x\leq a_{2n-1}$).

산의 경계는 $y\geq 0$ 영역에 있다고 보장된다.

준이가 $m$분 후에 태양을 볼 수 있게 하는 가장 작은 정수 $m$을 정확히 하나 출력한다.

그림: 첫 번째 예제의 그림