P15640 [ICPC 2022 Tehran R] Simplification

Amin records the price of his stock every now and then as a data point $(t_{i}, p_{i})$ in his notebook, where $p_{i}$ is the price of his stock at day $t_{i}$. The sequence of these data points represents a piecewise-linear function $F$ displaying the history of prices over a period of time. Indeed, $F$ connects every pair of consecutive points by a straight line segment. If the price is not recorded for some day $t$, $F(t)$ can be used as an estimate instead. His collected data is getting larger and larger as he has been tracking the price of his stock over a long period of time. Therefore, he has decided to reduce his data by throwing away some of his recoded data points and constructing a new piecewise-linear function $F'$ with the remaining points. $F'$ is a so-called "simplification" of $F$. Amin wants to create the simplification in such a way that $F'$ is a good approximation for $F$. To this end, he has defined an error measure as follows. Let $F$ be defined over a strictly increasing sequence $L = \langle t_{1}, \ldots, t_{n} \rangle$ of days, and $F'$ be defined over a subsequence $L' = \langle t'_{1}, \ldots, t'_{m} \rangle$ of $L$, where $t'_{1} = t_{1}$, $t'_{m} = t_{n}$, and $F'(t'_{i}) = F(t'_{i})$ for $1 \leq i \leq m$. (We call $m$ the size of $F'$.) The error of $F'$ is defined as the maximum of $|F'(t_{k}) - F(t_{k})|$ for all $1 \leq k \leq n$. For example, in the following figure, we have $6$ data points, labeled $1$ through $6$, whose coordinates are the same as those presented in the second sample input, and $F'$ is a simplification of $F$ of size $3$ with data points $1$, $4$ and $6$. In this figure, $F$ is depicted by solid lines, and $F'$ by dashed lines. The error measure for $F'$ is realized by the vertical distance of point $2$ to $F'$. :::align{center}  ::: Amin's goal is to minimize the size of $F'$, while the error of $F'$ is bounded by a given value $\delta$.

The first line of input contains a positive integer $n$ ($2 \leqslant n \leqslant 2000$) that shows the size of $F$. Each of the next $n$ lines contains two integers $t_{i}$, $p_{i}$ ($1 \leqslant t_{i}, p_{i} \leqslant 10^{6}$), where $p_{i}$ is the price of the stock at day $t_{i}$. The last line contains the error limit $\delta$ which is a non-negative integer at most $10^{6}$.

In the output, print the minimum possible size of $F'$.