Migrated from Lutece 3046 通信方案

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

可以被视为二维笛卡尔坐标系的地图中，有 $n$ 个信号塔(编号从 $1$ 到 $n$ )，信号塔 $i$ 的坐标为 $(x_i,y_i)$ 。

建立一个信号塔接受方案步骤如下：

1. 将这些信号塔分成编号连续的 $k$ 组，其中每个信号塔只会出现在一个组中。
2. 对于分好的每一组，在地图上选择一个位置建立一个接收站来接受这一组信号塔发出的信号。建立某组的接受站的花费是这个接收站与该组内距离这个接收站最远的信号塔之间的距离。该距离为欧氏距离，也就是说对于两点 $(x_1,y_1),(x_2,y_2)$ ，它们之间的距离为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ 。

一个方案的花费等于该方案中建立所有接收站的花费总和。

可以看出，如何分组以及如何选择接收站的位置至关重要。现在 $n,k$ 和每个点的坐标已知，你需要求出建立信号塔接受方案的最小花费。

特别地，在本题中，编号为 $1$ 的信号塔的坐标 $x_1$ 会直接给出，剩余的信号塔坐标将以以下形式获取： $x_i = y_{i−1} × 233811181 + 1(mod(2^{31} − 1)), ∀i ≥ 2.$ $y_i = x_i × 233811181 + 1(mod(2^{31} − 1)), ∀i ≥ 1.$

Input

在第一行包含三个整数， $n,k,x_1$ ，分别表示信号塔的个数，接受方案需要分的组数，编号为 $1$ 的信号塔的横坐标。

Output

输出一个浮点数表示最小花费，请使用科学计数法的方式输出，保留六位有效数字（即 printf("%.5e\n", ans)）。

Samples

100 23 213

1.31935e+09

Constraints

$1≤k≤n≤2000, 1≤x_1≤8831$

Resources

2023 UESTC ICPC Training for Geometry