급여 정산

바이트소프트(Bajtosoft)는 $n$명의 직원을 고용하고 있다. 회사가 진행하는 프로젝트는 기밀이라 모든 직원이 서로를 아는 것은 아니다. 같은 프로젝트의 연속된 단계를 담당하는 직원끼리만 서로 안다.

모든 프로젝트는 순차적으로 진행된다. 먼저 $1$번 직원(팀장)이 초안을 만들어 $2$번 직원에게 넘기고, $2$번 직원은 자기 작업을 마친 뒤 결과물을 $3$번 직원에게 넘긴다. 이런 식으로 계속되어 마지막에는 프로젝트가 $n$번 직원에게 도달하고, $n$번 직원이 작업을 마친 뒤 완성품을 다시 팀장($1$번 직원)에게 넘긴다.

각 직원은 계약서에 받기로 되어 있는 급여 액수가 적혀 있다. 그런데 회사가 계약을 늘 정확히 지키지는 않는다. 지급하는 총액은 항상 직원들에게 줘야 할 총액과 같지만, 늘 올바른 사람에게 지급되는 것은 아니다. 어떤 사람은 계약에 보장된 것보다 적게 받고, 다른 사람은 더 많이 받는 일이 자주 생긴다.

다행히 직원들은 정직해서, 급여가 지급될 때마다 서로 금액을 정산하여 최종적으로 각자가 계약에 보장된 만큼 정확히 받도록 하기로 약속했다.

문제는 한 가지다. 돈은 서로 아는 직원끼리만 주고받을 수 있다. 즉 $1 < i < n$인 각 $i$에 대해 $i$번 직원은 $i-1$번과 $i+1$번 직원하고만 돈을 주고받을 수 있고, $1$번 직원은 $2$번과 $n$번 직원과, $n$번 직원은 $n-1$번과 $1$번 직원과 거래할 수 있다.

이런 정산에는 여러 번의 거래가 필요하기 때문에, 바이트소프트 직원들은 독립 프로그래머인 당신에게 급여가 지급될 때마다 정산에 필요한 최소 거래 횟수를 구하는 프로그램을 만들어 달라고 부탁했다.

여기서 직원들은 거래할 때, 이번 급여로 회사에서 받은 돈과 이전 거래에서 다른 직원에게 받은 돈만 사용한다고 가정한다.

표준 입력의 첫 줄에는 바이트소프트의 직원 수를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어진다.

이어지는 $n$개의 줄에는 각각 두 정수 $a_i$와 $b_i$ ($1 \le a_i, b_i \le 1000$)가 공백 하나로 구분되어 주어진다. 이는 각각 $i$번 직원이 계약에서 보장받은 급여와 실제로 받은 금액(단위: 바이트탈러)이다. $a_1 + a_2 + \dots + a_n = b_1 + b_2 + \dots + b_n$임이 보장된다.

표준 출력의 첫 줄이자 유일한 줄에, 모든 거래를 마친 뒤 각 직원이 계약에 보장된 금액을 정확히 갖게 되는 상태에 도달하기 위해 서로 아는 직원끼리 필요한 최소 거래 횟수를 정수 하나로 출력한다.

어떤 거래 집합으로도 그런 상태에 도달할 수 없다면 "NIE"라는 한 단어를 출력한다.

예시 설명: 모든 급여는 두 번의 거래로 정산된다. $3$번 직원이 $2$번 직원에게 $1$바이트탈러를 주고, $1$번 직원이 $4$번 직원에게 $3$바이트탈러를 준다.