시간 관리

진영이는 캠프 조교가 된 뒤 시간을 효율적으로 관리해야 한다는 사실을 깨달았다. 하루 동안 해야 할 일은 모두 N개이며, 진영이는 이 일들에 1번부터 N번까지 번호를 붙였다.

각 일 i에는 처리하는 데 정확히 T_i 시간이 걸리고, S_i시 이내에 끝내야 하는 마감 시간이 있다. 진영이는 0시부터 활동을 시작할 수 있으며, 동시에 두 개 이상의 일을 처리할 수 없다.

진영이는 모든 일을 각자의 마감 시간 안에 끝낼 수 있는 범위에서 최대한 늦게 일을 시작하고 싶다. 모든 일을 제때 끝낼 수 있을 때, 진영이가 일을 시작할 수 있는 가장 늦은 시각을 구하라.

첫째 줄에 일의 수 N이 주어진다.

다음 N개의 줄 중 i번째 줄에는 i번째 일에 대한 두 정수 T_i와 S_i가 주어진다.

모든 일을 마감 시간 안에 끝낼 수 있도록 일을 시작하는 가장 늦은 시각을 출력한다.

0시부터 시작해도 모든 일을 끝낼 수 없다면 -1을 출력한다.

• 1 <= N <= 1,000
• 1 <= T_i <= 1,000
• 1 <= S_i <= 1,000,000