서울에는 한강이라는 이름의 강이 동서 방향으로 흐른다.

북쪽 강변에는 서쪽에서 동쪽으로 가는방향으로 1 부터 N 까지 번호가 붙은 N 개의 보트 학교가 있다.

한 학교의 보트들은 색이 같고, 따라서 서로 구별할 수 없다. 다른 학교의 보트들은 반드시 색이 다르고, 따라서 항상 구별이 된다.

i 번 학교는 축제에 보트를 하나도 내보내지 않을 수 있다.

만약 i 번 학교가 축제에 보트를 내보내기로 했다면 ai 개 부터 bi 개 사이(양 끝 포함)의 보트를 내보낼 수 있다. (ai ≤ bi)

한가지 중요한 조건은, i 번 학교가 보트를 내보내기로 한 경우에는 i 보다 번호가 작은 그 어떠한 학교가

내보낸 보트 수 보다 많은 수의 보트를 내보내야 한다는 것이다. (보트를 내보낸 i 보다 번호가 작은 학교가 존재하는 경우에 적용된다.)

Task

모든 학교의 ai 와 bi 값을 입력으로 받아서 학교들이 보트를 내보낼 수 있는 모든 가능한 경우의 수를 계산하는 프로그램을 작성하라.

단, 최소한 한 학교는 보트를 내보내는 경우들만 계산에 포함된다.

Boat timer 1s memory 64MB

Boat 1s 64MB