Settling Salaries

Bajtosoft employs $n$ workers. Because the projects it develops are confidential, not all of them know one another. Two workers know each other only if they handle consecutive stages of the same project.

Every project is developed sequentially: worker $1$ (the team lead) makes the first draft and passes it to worker $2$; after finishing their part, worker $2$ passes the result to worker $3$, and so on, until the project reaches worker $n$, who completes it and hands the finished product back to the team lead (worker $1$).

Each worker has a salary written into their contract. However, the company does not always honor the contract exactly. It always pays out the correct total amount, but not always to the right people: it often happens that one person receives less than their contract guarantees while another receives more.

Luckily the workers are honest, so they agreed that after every payout they will settle the amounts among themselves so that in the end everyone receives exactly what their contract guarantees.

There is just one catch: money can be transferred only between workers who know each other. That is, for every $1 < i < n$, worker $i$ may give money to or receive money from only workers $i-1$ and $i+1$; worker $1$ may transact with workers $2$ and $n$; and worker $n$ may transact with workers $n-1$ and $1$.

Because each such settlement requires many transactions, the Bajtosoft workers have asked you, an independent programmer, to write a program that after each payout determines the minimum number of transactions needed to settle the accounts.

We assume that in these transactions workers use only the money they received from the company in the given payout together with the money they received from other workers in earlier transactions.

The first line of standard input contains a single integer $n$ ($1 \le n \le 10^6$), the number of Bajtosoft workers.

Each of the next $n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 1000$), separated by a single space: the salary of the $i$-th worker guaranteed by the contract and the amount they actually received (both in bytalers). You may assume that $a_1 + a_2 + \dots + a_n = b_1 + b_2 + \dots + b_n$.

Print, in the first and only line of standard output, a single integer: the minimum number of transactions between workers who know each other that reaches a state where every worker ends up (after all transactions) with exactly the amount guaranteed by their contract.

If no set of transactions can reach such a state, print the single word "NIE".

Explanation of the sample: All salaries are settled in two steps: worker $3$ gives worker $2$ one bytaler, and worker $1$ gives worker $4$ three bytalers.