在你的帮助下，SingleDog们终于进入了计算中心内部，他们惊讶的发现，计算中心的核心——AlphaGo的三台主机所在的地方，居然是一个多维空间！

简单点说，核心是 $n\le 5$ 维空间里一个点集，位于一个 $n$ 维长方体的方框内部。方框内部由所有满足 $l_i\le x_i\le r_i$ 的点 $(x_1,x_2,\cdots ,x_n)$ 构成，而核心则由所有位于方框内部且满足 $x_i-x_j\ge a_{i,j}$ 的点$(x_1,x_2\cdots ,x_n)$ 构成，其中 $l_i,r_i,a_{i,j}$ 均为给定的整数。

现在SingleDog们想知道的就是这个核心的“体积”占方框的体积的比例。

为了方便理解题意，一个等价的题目描述是：

设 $x_1,x_2,\cdots ,x_n$ 是 $n$ 个实数变量，其中第 $i$ 个变量 $x_i$ 在区间 $[l_i,r_i]$ 内均匀随机生成，所有 $l_i$ 和 $r_i$ 均为给定的整数且 $l_i\le r_i$（约定 $l_i=r_i$ 时，$[l_i,r_i]$ 表示单元素集合 $\{l_i\}$）。

给定 $n\times n$ 的整数矩阵，矩阵的每个元素代表一个约束，其中第 $i$ 行第 $j$ 列的元素 $a_{i,j}$ 代表约束 $$x_i-x_j\ge a_{i,j}$$

求这 $n\times n$ 个约束同时被满足的概率。

输入格式

第一行包含一个正整数 $n$，表示实数变量个数。

接下来 $n$ 行，第 $i$ 行两个整数 $l_i,r_i$，描述第 $i$ 个区间。

接下来 $n$ 行，每行 $n$ 个整数，给出整数矩阵 $a_{i,j}$。

输出格式

输出一行，包含一个实数，表示所求的概率。

你的答案与参考答案的绝对误差不超过 ${10}^{-7}$ 时被认为是正确的。

样例一

input

1
0 10
-10

output

1.000000000000

explanation

无论变量 $x_1$ 的值是多少，约束 $x_1-x_1\ge -10$ 恒成立，故满足约束的概率为 $1$。

样例二

input

2
5 5
3 7
0 1
-3 0

output

0.2500000000

explanation

$x_1=5$，$3\le x_2\le 7$。仅当 $3\le x_2\le 4$ 时才能同时满足所有约束，故满足所有约束的概率为 $\frac{1}{4}=0.25$。

样例三

input

2
4 5
3 6
-10 2
-10 -10

output

0.0000000000

explanation

满足 $4\le x_1\le 5$，$3\le x_2\le 6$ 的 $x_1,x_2$ 有无穷多个，但只有一组值 $x_1=5,x_2=3$ 是满足约束的，故满足约束的概率为 $0$。

样例四

input

2
3 10
0 8
-1 1
-7 0

output

0.5982142857

explanation

满足约束的概率为 $\frac{67}{112}$。你输出的答案应当在 $[\frac{67}{112}-{10}^{-7},\frac{67}{112}+{10}^{-7}]$ 范围内。

样例五

input

3
0 10
2 10
2 9
0 -9 -10
4 0 -3
1 -4 0

output

0.1491071429

样例六

input

4
0 5
0 9
4 10
0 5
0 -8 -9 -5
1 0 -4 3
1 -6 0 3
-4 -10 -10 0

output

0.2622839506

样例七

input

5
0 10
0 10
4 4
0 9
0 7
-10 -9 -10 -10 -10
-10 -10 2 -10 -10
-10 -10 -10 1 -10
-10 -10 -10 -10 -5
-10 -10 -10 -10 -10

output

0.1191269841

样例八

input

5
0 2
1 8
7 10
2 7
6 10
0 -10 -10 -9 -10
-10 0 -7 -4 -8
3 3 0 1 -6
3 -6 -5 0 -5
-2 3 -9 1 0

output

0.1713095238

限制与约定

由于一些原因，本题使用捆绑测试。每个子任务有若干个测试点，分为 8 个子任务，你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

对于所有数据，$1\le n\le 5$，$0\le l_i\le r_i\le 10$，$-10\le a_{i,j}\le 10$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载