건초 더미에 갇히다 (실버)

농부 존은 N개의 커다란 건초 더미(1 <= N <= 100,000)를 배송받아 길을 따라 여러 위치에 놓아 두었다. 각 건초 더미 j는 크기 S_j와 일차원 길 위의 서로 다른 위치 P_j를 가진다. 소 베시는 현재 건초 더미가 없는 위치 B에 있다.

베시는 건초 더미의 위치까지는 길을 따라 자유롭게 이동할 수 있지만 더미를 통과할 수는 없다. 예외적으로, 같은 방향으로 D만큼의 거리를 달리면 충분한 속도가 붙어서 크기가 D보다 엄밀히 작은 건초 더미를 뚫고 지나가 영구히 없앨 수 있다.

FJ는 베시가 가장 왼쪽 또는 가장 오른쪽 더미를 절대 뚫지 못하게 하여 계속 갇혀 있게 만들고 싶다. FJ는 자신이 선택한 하나의 더미에 건초를 추가할 수 있다. 베시가 계속 갇혀 있도록 보장하기 위해 어떤 더미에 추가해야 하는 크기의 최솟값을 구해 FJ를 도와주자.

첫째 줄에 N과 베시의 초기 위치 B가 주어진다. 다음 N개의 줄에는 각각 건초 더미를 나타내는 두 정수인 크기와 위치가 주어진다. 모든 크기와 위치는 1...10^9 범위이다.

베시가 탈출하지 못하도록 FJ가 추가해야 하는 건초의 최소량을 하나의 정수로 출력한다. 탈출을 막는 것이 불가능하면 -1을 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > US Open > Silver