모바일 광고 입찰

면접 대비

시간 제한2초메모리 제한1024 MB

요약

N개의 (A_i, B_i) 쌍이 주어질 때, A_i + X >= B_i를 만족하는 지면이 K개 이상이 되는 가장 작은 음이 아닌 정수 X를 구한다. 즉 B_i - A_i를 0 이상으로 자른 값 중 K번째로 작은 값이다.

난이도: 보통10점 중 4점
유형: 정렬, 이분 탐색, 배열, 그리디
정답자: 아직 제출이 없습니다

문제

모바일 광고 시장에서 광고 지면의 권리는 실시간 경매를 통해 결정된다. 이 경매에서는 각 지면에 대해 광고를 게재하고자 하는 회사들이 입찰가를 제시하며, 최고 입찰가를 제시한 회사가 해당 지면의 광고 권리를 얻는다. 이 과정은 전 세계 수많은 광고지면을 실시간으로 분석하고 입찰하는 기술적 도전을 포함한다.

MOLOCO는 고객사가 모바일 광고 시장에 접근할 수 있도록 도와주는 “MOLOCO 클라우드 DSP” 서비스를 운영한다. 이 서비스는 머신러닝을 기반으로 하여 초당 수백만 건 이상의 광고지면 입찰 요청을 처리한다. MOLOCO는 고객사들을 대신하여 입찰에 참여하며, 고객사가 최적의 가격으로 광고지면을 구매할 수 있도록 지원한다.

당신은 MOLOCO에서 클라우드 DSP 서비스를 개선하는 일을 맡고 있으며, 당신의 목표는 과거 중요한 광고지면 $N$ 개에 대한 입찰 데이터를 분석하여, 입찰 가격 결정 로직을 개선하는 것이다.

각 광고지면 $i$ 에 대해 MOLOCO가 제시한 입찰 가격 $A\_i$ 와 MOLOCO의 입찰가를 제외한 다른 모든 입찰가 중 최고 가격 $B\_i$ 가 주어진다. 당신은 MOLOCO가 모든 입찰가를 일괄적으로 $X(\ge 0)$ 만큼 올렸을 때, (즉, MOLOCO의 입찰가를 $A\_i$ 에서 $A\_i+X$ 로 일괄적으로 올리는 것이다.) $K$ 개 이상의 지면을 낙찰받게 되는 가장 작은 음이 아닌 정수 $X$ 를 찾고자 한다. 단, 같은 지면에 대해 MOLOCO의 입찰가와 다른 회사의 최고 입찰가가 같을 경우 MOLOCO가 낙찰받는다고 가정한다.

입력

첫 번째 줄에는 전체 분석 대상 광고 지면의 수 $N$ 과 목표 낙찰 지면 수 $K$ 가 공백으로 구분되어 주어진다.

다음 $N$ 개의 줄에 광고지면 $i$ 에 대한 정보 $A\_i$ 와 $B\_i$ 가 공백으로 구분되어 차례로 주어진다.

출력

MOLOCO의 입찰가를 일괄적으로 $X$ 만큼 올렸을 때, 최소 $K$ 개 이상의 지면을 낙찰받는 음이 아닌 최소 정수 $X$ 를 출력하라.

제한

주어지는 모든 수는 정수이다.
$1\le N\le 100\\, 000$
$1\le K\le N$
$1\leq A\_i,B\_i\leq 10^9$ $(1\le i\le N)$

예제2

예제 1
입력
```
3 2
3 1
2 1
1 2
```
예상 출력
```
0
```
예제 2
입력
```
3 2
10 30
21 19
10 12
```
예상 출력
```
2
```