题目背景

「爆ぜろリアル！弾けろシナプス！パニッシュメント......ディス、ワールド！」
「爆裂吧，现实！粉碎吧，精神！放逐这个世界！」

题目描述

Rikka 坚信，她的父亲在「不可视境界线」中，等待着她的到来。在 Rikka 的梦里，「不可视境界线」出现了，那是 $n$ 个圆组成的图形。

具体地，有一个平面直角坐标系，坐标系的 $x$ 轴上有 $n$ 个点，第 $i$ 个点的坐标为 $(x_i,0)$。

Rikka 以每一个点作为圆心，作了 $n$ 个半径为 $r$ 的圆。她本想让你帮她计算这 $n$ 个圆的面积并，但是这个问题太简单了。

在一番思考后，Rikka 想让你计算出选出 $k$ 个圆后（即删除 $n-k$ 个圆），圆的面积并的最大值。

对于所有数据，有 $n,k\leq 10^5$，$r\leq 10^4$，$0\leq x_i\leq 10^9$，$x_i$ 为整数且不重复。保证输入的 $x_i$ 单调递增。

因为答案太大了，Rikka 考虑到你的电脑无法保持高精度，所以只要你的答案与标准答案的 相对误差 小于 $5\times 10^{-8}$，你的答案即被视为是正确的。

经过误差分析，本题保证使用原生 cmath 函数不会出错，请注意控制程序精度误差。

输入格式

共 $2$ 行。

第 $1$ 行输入 $3$ 个整数 $n$，$k$，$r$。

第 $2$ 行输入 $n$ 个整数 $x_1\ldots x_n$。

输出格式

一行 $1$ 个实数，表示所求答案，保证答案小于 $10^{14}$。

8 5 2
1 3 7 11 15 21 27 33

62.83185307

8 5 8
1 3 7 11 15 21 27 33

686.19551835

提示

样例解释 1

显然，可以选出 $5$ 个不相交的半径为 $2$ 的圆。

子任务

对于 $100\%$ 的数据，$n,k\leq 10^5$，$r\leq 10^4$，$0\leq x_i\leq 10^9$。

本题采用捆绑测试，共有 $7$ 个子任务，各子任务的分值和限制如下：

子任务 $1$（$11$ 分）：$k=n$。

子任务 $2$（$13$ 分）：$n,k,r \leq 100$。

子任务 $3$（$6$ 分）：$n,k \leq 1000$，$r\leq 20$。

子任务 $4$（$15$ 分）：$n,k,r \leq 2000$，保证数据随机生成。

子任务 $5$（$23$ 分）：$r\leq 20$。

子任务 $6$（$12$ 分）：$k\leq 20$，$x_n \leq kr$。

子任务 $7$（$20$ 分）：无特殊限制。

题目来源

MtOI2019 Extra Round T5

出题人：disangan233

验题人：suwAKow，_sys