Kakao Money

KakaoPay is a fintech service that lets you transfer money and make payments through KakaoTalk. KakaoPay offers a service called Kakao Money, which lets you charge and spend cash as much as you want. Muzi decided to start using Kakao Money today to spend cash conveniently. To use the service more easily, Muzi linked his own bank account, which has a balance of 10,100 won, to his Kakao Money account.

Initially, Muzi's Kakao Money balance is 0 won. When Muzi charges his balance from his bank account or receives a transfer from someone else, the Kakao Money balance increases, and this is called a deposit. When Muzi pays with Kakao Money or sends a transfer to someone else, the Kakao Money balance decreases, and this is called a withdrawal. In this problem, assume that there are no restrictions on deposits or withdrawals other than that the amount must be in units of 1 won. That is, ignore the real Kakao Money restrictions such as a balance limit of 2 million won and a daily transfer limit of 500,000 won.

When $x$ won is deposited, Muzi's Kakao Money balance increases by $x$ won. However, withdrawing $x$ won works differently. If the balance is at least $x$ won, subtract $x$ won from the balance. But if the balance is less than $x$ won, Kakao Money cannot cover the amount internally, so it must pull money from the linked bank account. To do this, Kakao sets a minimum charge unit $M$: it keeps pulling $M$ won from the bank account until the balance is at least $x$ won, then subtracts $x$ won from the balance. $M$ is a positive integer.

For example, suppose $M = 10{,}000$, Muzi's balance is 1,500 won, and he wants to withdraw $x = 17{,}000$ won. Since Muzi's balance cannot cover $x = 17{,}000$ won, Kakao Money first pulls $M = 10{,}000$ won from Muzi's bank account, making the balance 11,500 won. But 11,500 won still cannot cover $x = 17{,}000$ won, so Kakao Money pulls another $M = 10{,}000$ won from Muzi's bank account, making the balance 21,500 won. Now it can withdraw 17,000 won, so it subtracts $x = 17{,}000$ won from the balance. In the end, Muzi's Kakao Money balance becomes $21{,}500 - 17{,}000 = 4{,}500$ won.

Apart from the transaction history kept by Kakao Money, Muzi has been writing his own deposit and withdrawal log since he started using Kakao Money. This log consists of $N$ pairs of integers $(a_i, b_i)$, stored in chronological order. Muzi is careful, so he believes he has not missed any deposit or withdrawal in the log. The meaning of each pair is as follows.

• If $a_i > 0$, then $a_i$ won was deposited into Muzi's Kakao Money. As a result of the deposit, the balance was $b_i$ won.
• If $a_i < 0$, then $-a_i$ won was withdrawn from Muzi's Kakao Money. As a result of the withdrawal, the final balance was $b_i$ won.
• There is no case where $a_i = 0$.

For the example above, the pair $(-17{,}000, 4{,}500)$ would have been added to Muzi's log.

However, Muzi worries that he might not be managing his log correctly, so he wants to simply check whether the log is consistent. His idea is to look only at the log and determine whether there exists a minimum charge unit $M$ that makes the log valid, meaning it does not create a contradiction, and if so, what its value is. Write a program to do this for Muzi.

The first line gives the number of pairs $N$ in Muzi's log ($1 \le N \le 300{,}000$).

The next $N$ lines give the log Muzi wrote. The $i$-th line ($1 \le i \le N$) contains two integers $a_i$ and $b_i$ ($-10^{18} \le a_i \le 10^{18}$, $a_i \ne 0$, $0 \le b_i \le 10^{18}$) separated by a single space.

If a valid minimum charge unit $M$ exists ($1 \le M \le 9 \times 10^{18}$), print $M$ on the first line. If there are multiple possible values, print any one of them that is at most $9 \times 10^{18}$.

If it does not exist, print -1.