빵
시간 제한1초메모리 제한1024 MB
각 가게의 이동 시간 A와 빵이 도착하는 시간 B가 주어질 때, 빵을 살 수 있는 가장 이른 시간을 구합니다. 살 수 있는 방법이 없으면 -1을 출력합니다.
문제
KOI 빵은 프로그래밍을 공부하는 학생들에게 인기가 많다. 맛있을 뿐만 아니라 안에 프로그래밍에 도움이 되는 힌트가 담겨 있다.
KOI 빵이 가게에 들어오면 사람들이 바로 모두 사 간다. 빵을 사려면 빵이 오기 전에 가게에서 기다리거나, 빵이 들어오는 순간에 맞춰 가야 한다.
가게가 개 있다. 각 가게마다 현재 위치에서 가게까지 가는 데 걸리는 시간과, 그 가게에 KOI 빵이 들어올 때까지 남은 시간이 주어진다. 빵이 도착하는 순간이나 그 전에 가게에 도착하면 KOI 빵을 살 수 있다. 빵이 도착한 뒤에 가게에 도착하면 이미 빵이 없다.
지금부터 몇 분 뒤에 KOI 빵을 구할 수 있는지 가장 빠른 시점을 구하는 프로그램을 작성하시오. KOI 빵을 구할 수 없을 수도 있다.
입력
첫 번째 줄에 가게의 수 이 주어진다.
다음 개의 줄에는 공백으로 구분된 정수 와 가 한 줄에 하나씩 주어진다. 는 현재 위치에서 가게까지 가는 데 걸리는 시간이고, 는 그 가게에 빵이 들어올 때까지 남은 시간이다.
출력
KOI 빵을 살 수 없다면 -1을 출력한다.
살 수 있다면 지금부터 빵을 구하는 데 걸리는 최소 시간을 출력한다.
제한
주어지는 모든 수는 정수이다.
- 각 가게에 대해, 현재 위치에서 이 가게까지 가는 데 걸리는 시간을 , 이 가게에 빵이 들어올 때까지 남은 시간을 라고 하자.