단순화

아민은 가끔씩 자신의 주식 가격을 노트에 데이터 점 $(t_i, p_i)$로 기록한다. 여기서 $p_i$는 $t_i$일의 주식 가격이다. 이 데이터 점들은 일정 기간의 주가 변화를 나타내는 구간별 선형 함수 $F$를 이룬다. $F$는 연속한 두 점을 직선 선분으로 잇는다. 어떤 날 $t$의 가격이 기록되지 않았다면 $F(t)$를 대신 추정값으로 쓸 수 있다.

그는 오랜 기간 주가를 추적해 왔기 때문에 모아 둔 데이터가 계속 늘어났다. 그래서 기록된 점 일부를 버리고, 남은 점으로 새로운 구간별 선형 함수 $F'$을 만들어 데이터를 줄이기로 했다. $F'$은 $F$의 단순화이며, 그는 $F'$이 $F$를 잘 근사하기를 원한다. 그는 오차를 다음과 같이 정의한다.

$F$가 날짜의 엄격한 증가 수열 $L = \langle t_1, \ldots, t_n \rangle$ 위에 정의되어 있고, $F'$이 $L$의 부분수열 $L' = \langle t'_1, \ldots, t'_m \rangle$ 위에 정의되어 있다고 하자. 여기서 $t'_1 = t_1$, $t'_m = t_n$이고, $1 \leq i \leq m$에 대해 $F'(t'_i) = F(t'_i)$이다. $m$을 $F'$의 크기라고 한다. $F'$의 오차는 모든 $1 \leq k \leq n$에 대한 $|F'(t_k) - F(t_k)|$의 최댓값이다.

아래 그림은 1번부터 6번까지 번호가 붙은 데이터 점을 보여준다. 점 1, 4, 6을 사용하는 크기 3의 단순화가 $F'$이다. $F$는 실선, $F'$은 점선으로 그려져 있다. $F'$의 오차는 점 2에서 $F'$까지의 수직 거리다.

아민의 목표는 $F'$의 오차가 주어진 값 $\delta$ 이하가 되도록 $F'$의 크기를 최소로 만드는 것이다.

첫 줄에 $F$의 크기를 나타내는 양의 정수 $n$ ($2 \leq n \leq 2000$)이 주어진다. 다음 $n$개의 줄에는 정수 $t_i$와 $p_i$ ($1 \leq t_i, p_i \leq 10^6$)가 한 줄에 하나씩 주어진다. 마지막 줄에는 오차 한도 $\delta$가 주어지며, $\delta$는 $10^6$ 이하의 음이 아닌 정수다.

$F'$이 가질 수 있는 최소 크기를 출력한다.