Branory 和 Gredon 从远房亲戚那里继承了一个苹果园。当他们第一次造访果园时，惊喜地发现果园里所有 $n$ 棵苹果树的树干直径都恰好为 $d$。

他们觉得照顾全部 $n$ 棵树工作量太大，因此决定只保留其中的 $k$ 棵。为了防止野生动物进入果园，他们将建造一条单一连续的栅栏，将保留的 $k$ 棵树围起来。栅栏可以弯曲成任何形状，但其总长度必须尽可能小。

Gredon 前去购买栅栏材料，而 Branory 留下来拔除果园中的树木。Gredon 想要购买最少数量的栅栏来围住保留的 $k$ 棵苹果树的树干，但他意识到自己并不知道 Branory 会拔除哪些树！Gredon 知道 Branory 会随机拔除树木，直到恰好剩下 $k$ 棵树。Gredon 需要购买的围住剩余树木的栅栏长度的期望值是多少？

图 A.1：样例 3 的树木示意图。右图显示了拔除左上角树木后的最优栅栏。

输入格式

输入的第一行包含三个整数 $n$、$k$ 和 $d$（$1 \le k \le n \le 2000$，$1 \le d \le 100$），其中 $n$ 是果园中原本的苹果树数量，$k$ 是将要保留的树木数量，$d$ 是每棵树的直径。

接下来的 $n$ 行，每行包含两个实数 $x$ 和 $y$，表示一棵树干中心的坐标。所有坐标的绝对值均不超过 $10^4$，且恰好给出两位小数。保证树干之间不会重叠或接触。

输出格式

输出一个实数，表示 Gredon 需要购买的栅栏长度的期望值。如果你的答案与标准答案的相对或绝对误差不超过 $10^{-6}$，则视为正确。

样例

输入样例 1

3 1 10
1.00 1.00
30.00 31.50
55.00 67.50

输出样例 1

31.4159265359

输入样例 2

4 3 10
-100.00 -100.00
0.00 0.00
100.00 100.00
200.00 200.00

输出样例 2

738.5227077224

输入样例 3

4 3 20
100.00 100.00
0.00 0.00
100.00 0.00
0.00 100.00

输出样例 3

404.2532093091

说明

样例 1 说明

无论保留哪棵树，Gredon 都需要购买足够的栅栏来围住那一棵树。