Maximum Grid Path with Additional Points

Given n integer points on a 2D plane, and the ability to add k additional integer points (placing them arbitrarily), you are to form a sequence of points chosen from the union of these n and k points. The sequence must satisfy that the Euclidean distance between any two consecutive points is exactly 1 and the move from one point to the next is either a right move (from (x, y) to (x+1, y)) or an up move (from (x, y) to (x, y+1)). In other words, if a point in the sequence is p=(x, y) and the next point is q, then either q = (x+1, y) or q = (x, y+1). The goal is to maximize the length (i.e. the number of points) in such a sequence. Note that the original points are given for free; however, every point you add counts against the limit k. If no original point is available (n=0), you may only use the k free points (in which case the maximum sequence length is k, because each point must be explicitly added).

The idea to solve the problem is as follows. A legal grid path (using only right and up moves) from point S=(a, b) to T=(A, B) must have length L = (A - a) + (B - b) + 1. If among the points on this path some are original (don’t count toward the free additions) and the rest must be added, then if r is the count of original points along some path (which can be made to cover the rectangle between two original points) the number of free points needed is L - r. Since you may add at most k points, you must have L - r ≤ k. One strategy is to choose two original points p and q (with p’s coordinates not exceeding q’s coordinate‐wise) so that the rectangle they span allows you to “use” a number of original points r and then fill the missing spots with free points. Of course, you can always consider the possibility of a path using only a single original point (or none, if n=0) in which case you can extend the path by k free points, achieving a sequence of length k+1 (if at least one original point exists). The answer is the maximum sequence length achievable under these constraints.

Formally, if you select two original points p and q with p = (x1, y1) and q = (x2, y2) such that x1 ≤ x2 and y1 ≤ y2, then the full grid path from p to q has length L = (x2 - x1) + (y2 - y1) + 1. Let r be the number of original points lying in the rectangle [x1, x2] × [y1, y2]. Then, you can form a valid sequence covering the entire rectangle provided that L - r ≤ k. The answer is the maximum such L over all possible pairs, with the single-point extension (k+1) taken into account as well (and, for n = 0, the answer is k).

inputFormat

The first line contains two integers n and k. Then follow n lines, each containing two integers x and y denoting an original point. All points have integer coordinates.

outputFormat

Output a single integer representing the maximum length of a valid sequence.

sample

0 5

5