Description

Given n 2D points, select k points such that the value of max(x_¹, x₂, ..., x_k) + max(y₁, y₂, ..., y_k) is minimized. Here, (x₁, y₁), (x₂, y₂), ..., (x_k, y_k) are the coordinates of the selected k points.

Input

The first line contains two positive integers n and k.
The next n lines each contain two integers, representing the x and y coordinates of the n 2D points.

Constrain

• 0 < k ≤ n ≤ 10⁶
• 0 < x₁, x₂, ..., x_n ≤ 10⁶
• 0 < y₁, y₂, ..., y_n ≤ 10⁶

Output

Output the minimum value of max(x_¹, x₂, ..., x_k) + max(y₁, y₂, ..., y_k).

Remember to print a ‘\n’ at the end of the output.

HINT

Select points (1, 6), (4, 8), and (5, 9) such that max(1, 4, 5) + max(6, 8, 9) = 14. This is the optimal selection.

Sample Input  Download

Sample Output  Download

Tags

Discuss