King of Chairs

King Uija of Baekje lined up $N$ court ladies in the palace front yard. The palace has 3,000 court ladies, but the front yard is narrow, so only $N$ of them stand in the line.

The king wants to dress their hair. The work goes faster when a person behind can see the head of a person in front of her. A person sees the head of every person ahead of her who is shorter than she is. A person in between who is taller than her, or exactly as tall as her, does not block the view, so she also sees the heads of the shorter people further ahead. The number of viewings in one arrangement is therefore the number of ordered pairs (person behind, person in front) in which the person behind is strictly taller than the person in front.

Court lady $i$ has sitting height $S_i$ and standing height $H_i$. Each court lady sits on a chair with probability $1/2$ and stands with probability $1/2$, independently of every other court lady. Her height is $S_i$ while she sits and $H_i$ while she stands.

The king does not know who will sit and who will stand, so he cannot know the number of viewings, but he can know its expected value. He may put the court ladies in any order he likes. Write a program that finds the largest expected number of viewings he can reach.

The first line contains the number of court ladies $N$. ($2 \le N \le 3000$)

Each of the next $N$ lines contains the sitting height $S_i$ and the standing height $H_i$ of one court lady, separated by a space. ($1 \le S_i < H_i \le 10000$) The court ladies are given in order, starting with the one standing at the very back.

Print the largest expected number of viewings with exactly two digits after the decimal point. This value is always a multiple of $0.25$, so two digits represent it exactly.