Mobile Ad Bidding

Interview

Time limit2sMemory limit1024 MB

Summary

Find the smallest nonnegative integer X so that adding X to every bid A_i makes A_i + X at least B_i in at least K slots.

Level: Easy3 of 10
Topics: Sorting, Array
Solved: No attempts yet

Problem

Rights to ad slots in the mobile ad market are decided through real-time auctions. In each auction, companies that want to place an ad submit bids, and the company with the highest bid wins the ad rights for that slot. The process requires analyzing and bidding on countless ad slots worldwide in real time.

MOLOCO runs the MOLOCO Cloud DSP service, which helps clients reach the mobile ad market. The service uses machine learning to process several million bid requests per second. MOLOCO bids on behalf of its clients and helps them buy ad slots at the best price.

You are improving the bidding logic of the Cloud DSP service at MOLOCO. Your goal is to analyze the bidding data for $N$ past important ad slots and improve how the bid price is determined.

For each ad slot $i$ , you are given MOLOCO's bid $A_i$ and the highest bid $B_i$ among all other bids, excluding MOLOCO's. Suppose MOLOCO raises its bid in every slot by $X (\ge 0)$ , so its bid becomes $A_i+X$ instead of $A_i$ . Find the smallest nonnegative integer $X$ such that MOLOCO wins at least $K$ slots. If MOLOCO's bid ties the highest other bid in a slot, MOLOCO wins that slot.

Input

The first line contains $N$ and $K$ , separated by a space. Each of the next $N$ lines contains $A_i$ and $B_i$ for ad slot $i$ , separated by a space.

Output

Print the smallest nonnegative integer $X$ such that MOLOCO wins at least $K$ slots.

Constraints

All given numbers are integers.
$1\le N\le 100\,000$
$1\le K\le N$
$1\le A_i,B_i\le 10^9$ for $1\le i\le N$

Examples2

Example 1
Input
```
3 2
3 1
2 1
1 2
```
Expected output
```
0
```
Example 2
Input
```
3 2
10 30
21 19
10 12
```
Expected output
```
2
```