34036번 - 걸어가요

문제

영인이와 $N-1$명의 친구들은 걷는 것을 좋아한다. 오늘도 걸을 계획인 그들은, 그동안 겪었던 재미있는 이야기들을 나누고자 한자리에서 모이기로 했다.

그들은 1ドル$차원 좌표 평면 세계에서 살아간다. $i$번째 사람이 현재 서 있는 위치는 $X_i$이고, 양의 방향으로 $S_i$만큼 걸어가는 행위를 0ドル$회 이상 원하는 만큼 수행할 수 있다. 음의 방향이나 $S_i$가 아닌 단위만큼 걸어가는 행위는 법적으로 금지되어 있기에 할 수 없다.

영인이와 $N-1$명의 친구들이 한자리에서 모일 수 있는지 확인해 보자.

입력

첫째 줄에 사람의 수 $N$이 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐, $i+1$번째 줄에 $i$번째 사람의 현재 위치 $X_i,ドル 걸을 수 있는 단위 $S_i$가 공백으로 구분되어 주어진다.

출력

영인이와 $N-1$명의 친구들이 한자리에서 모일 수 있다면, 모일 수 있는 위치 중 최솟값을 출력한다.

모일 수 없다면 -1을 출력한다.

제한

• 2ドル \leq N \leq 8$
• 0ドル \leq X_i \leq 10,000円$
• 1ドル \leq S_i \leq 100$

입력으로 주어지는 수는 모두 정수이다.

힌트