AT_abc463_d [ABC463D] Maximize the Gap

There are $ N $ cloths on a number line. The $ i $ -th $ (1\le i\le N) $ cloth covers the interval $ \lbrack L _ i,R _ i\rbrack $ on the line. A point on the line may be covered by two or more cloths, or not covered by any cloth. Two cloths are said to overlap if some point on the line is covered by both of those cloths. For two cloths that do not overlap, define their **distance** as follows: - The minimum value of $ |p-q| $ over all points $ p $ covered by one cloth and all points $ q $ covered by the other cloth. For $ K $ cloths no two of which overlap, define their **score** as the minimum distance among all pairs of those cloths. Find the maximum possible score when choosing $ K $ cloths from the $ N $ cloths so that no two of the chosen cloths overlap. If it is impossible to choose $ K $ such cloths, output `-1`.

The input is given from Standard Input in the following format: > $ N $ $ K $ $ L _ 1 $ $ R _ 1 $ $ L _ 2 $ $ R _ 2 $ $ \vdots $ $ L _ N $ $ R _ N $

Output the answer.

### Sample Explanation 1 Choosing the second, fourth, and sixth cloths, no two of these overlap. The distance between the second and fourth cloths is $ 2 $ , the distance between the second and sixth cloths is $ 8 $ , and the distance between the fourth and sixth cloths is $ 2 $ , so the score of this choice is $ 2 $ . It is impossible to choose three cloths with a score of $ 3 $ or more, so output `2`. ### Sample Explanation 2 The given two cloths overlap, so it is impossible to choose two cloths so that no two overlap. Thus, output `-1`. Note that the first and second cloths overlap only at the single point $ 5 $ . ### Constraints - $ 2\le K\le N\le2\times10 ^ 5 $ - $ 0\le L _ i\lt R _ i\le10 ^ 9\ (1\le i\le N) $ - All input values are integers.