Problem D. Destiny of mathematician

Author:M. Sporyshev, A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  


Young mathematician Vasya has dropped out of university computer science degree, and now works as a janitor in a local software company. Part of his job is to lock offices after every programmer leaves.

Employees of software company work on a flexible schedule, everybody comes and goes when he pleases. However, Vasya's mother calls him every evening to know when Vasya will get home so as to prepare a hot supper for him.

For a long time Vasya was unsure how to answer, but finally he remembered something from his mathematical education. Vasya collected data about programmers' schedules. There are N programmers working in the company, numbered from 1 to N. Programmer number i may leave work in any integer-valued moment of time between li and ri inclusive with equal probability. All moments of time are measured in a whole seconds passed from the start of the day.

All programmers work on different projects so their schedules are independent from each other. Each day, Vasya leaves the office at the same moment as the last programmer.

Your program must, given data about programmers' schedules, calculate an expected value (also known as mathematical expectation) of the moment when Vasya will leave work.

Input file format

Input file contains a single integer N, followed by N pairs of integers li ri.

Output file format

Output file must contain a single floating point number  — expected value of the moment of Vasya's leaving, with at least 5 correct digits after decimal point.


1 ≤ N ≤ 8, 1 ≤ li ≤ ri ≤ 1000

ri − li ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 1 8
2 1 10 1 10

0.185s 0.090s 13