31246번 - 모바일 광고 입찰

문제

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

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)$

힌트