题目描述

乡村社区 Axes Point 的所有居民都住在两条平行街道之一，两条街道之间隔着一条绿色公园带。最近，当地监事会获得一笔补助，终于可以为小镇引入无线网络服务。

补助足以安装 $k$ 个无线接入点。监事会决定把它们排列在一条直线上，放置于县道 B 上；县道 B 位于林木覆盖的公园带中央，与两条住宅街道等距。

他们希望选择接入点位置，使用户到最近接入点的距离尽可能小。具体而言，需要最小化每名用户到其最近接入点距离平方的总和。

图 1 展示了两条街道、八名用户及其沿街位置，对应样例一。两街相距 $3$ 个单位，在正中间放置了两个接入点，使八个距离平方之和达到最小。

给定两条街上所有用户的位置、街道间距和接入点数量，求能够达到的最小距离平方和。

:::align{center} :::

输入格式

输入共三行。

第一行包含四个整数 $m,n,k,s$。其中 $1\le m,n\le 1000$，分别表示两条街上的用户数量；$1\le k\le\min(\max(m,n),100)$，表示接入点数量；$1\le s\le 50$，表示两条街道之间的距离。

第二行包含 $m$ 个浮点数 $x_1,x_2,\ldots,x_m$（$0\le x_i\le 1000$），表示第一条街上各用户沿街的位置。

第三行同样包含 $n$ 个浮点数，表示第二条街上的用户位置。第二行和第三行各自行内的所有数值互不相同，但同一位置可以同时出现在两行中。用户位置的小数点后不超过四位。

输出格式

输出一个浮点数，表示每名用户到最近的 $k$ 个接入点之一的距离平方之和的最小值。

若答案的绝对误差或相对误差不超过 $10^{-5}$，则认为正确。

4 4 2 3
0.5 1.0 3.0 3.5
1.0 2.5 3.0 3.5

18.86666667