Covering Grid Points with Straight Polylines

We are given a set of n points on the 2D integer grid. A polyline is drawn as a continuous stroke from left to right (i.e. with strictly increasing x‐coordinates) and is called a straight polyline if every segment makes an angle with the x–axis within ( [-45^\circ,45^\circ] ). In other words, if the polyline passes consecutively through points ((x_1,y_1)) and ((x_2,y_2)) with (x_1 < x_2), then it must satisfy [ |y_2 - y_1| \le x_2 - x_1. ]

A straight polyline may cover a subset of the given points if all these points appear (in some order) on the polyline. The problem is to determine the minimum number of straight polylines required so that every given point is covered by at least one polyline.

A useful observation is that for two points ((x_1,y_1)) and ((x_2,y_2)) (with (x_1 < x_2)) the condition [ |y_2 - y_1| \le x_2 - x_1 ] can be equivalently rewritten in terms of transformed coordinates. Define [ S=x+y, \quad D=x-y. ] Then the condition becomes [ S(x_1,y_1) \le S(x_2,y_2) \quad \text{and} \quad D(x_1,y_1) \le D(x_2,y_2). ] This means that a sequence of points forming a valid polyline corresponds to a chain in the partial order defined by sorting with respect to S (non–decreasing) and requiring D also be non–decreasing. One can show that the minimum number of chains required to cover all points equals the length of the longest strictly decreasing subsequence of the D–values when the points are sorted by S (and, if needed, by D in ascending order).

Your task is to compute this number.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le \text{some limit}\)), the number of points. Each of the following \(n\) lines contains two integers \(x\) and \(y\) representing the coordinates of a point.

outputFormat

Output a single integer — the minimum number of straight polylines required to cover all the given points.

sample

1
0 0

1