모바일 광고 입찰

모바일 광고 시장에서 광고 지면의 권리는 실시간 경매로 결정됩니다. 각 경매에서는 광고를 게재하려는 회사들이 입찰가를 제시하고, 최고 입찰가를 제시한 회사가 그 지면의 광고 권리를 얻습니다. 이 과정에는 전 세계의 수많은 광고 지면을 실시간으로 분석하고 입찰하는 기술적 과제가 따릅니다.

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

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

광고 지면 $i$마다 MOLOCO의 입찰가 $A_i$와, MOLOCO의 입찰가를 제외한 다른 모든 입찰가 중 최고 가격 $B_i$가 주어집니다. MOLOCO가 모든 지면에서 입찰가를 $X (\ge 0)$만큼 올려, 입찰가를 $A_i$에서 $A_i+X$로 올린다고 합시다. MOLOCO가 $K$개 이상의 지면을 낙찰받게 되는 가장 작은 음이 아닌 정수 $X$를 구하세요. 같은 지면에서 MOLOCO의 입찰가와 다른 회사의 최고 입찰가가 같으면 MOLOCO가 그 지면을 낙찰받습니다.

첫 번째 줄에 $N$과 $K$가 공백으로 구분되어 주어집니다. 다음 $N$개의 줄에는 광고 지면 $i$에 대한 $A_i$와 $B_i$가 공백으로 구분되어 차례로 주어집니다.

MOLOCO가 $K$개 이상의 지면을 낙찰받는 가장 작은 음이 아닌 정수 $X$를 출력하세요.

• 주어지는 모든 수는 정수입니다.
• $1\le N\le 100\,000$
• $1\le K\le N$
• $1\le A_i,B_i\le 10^9$ $(1\le i\le N)$