Axes Point 乡村社区的所有居民都居住在两条平行街道中的一条上，两条街道之间隔着一片绿地。最近，当地监事会获得了一笔拨款，终于可以为该镇提供无线服务。这笔拨款足以安装 $k$ 个接入点，监事会决定将它们放置在“B”县道上，这条路位于两条住宅街道中间的林带中。他们希望以一种能最小化用户与其最近接入点之间距离的方式来放置这些接入点。具体来说，他们希望最小化每个用户到其最近接入点距离的平方和。例如，图 B.1 展示了两条街道和八位客户及其沿街道的位置（这是第一个样例输入）。两条街道相距 3 个单位，两个接入点被放置在两条街道的中间，使得八个平方距离之和最小化。

图 B.1：展示接入点放置位置的样例输入 1

给定两条街道上所有客户的位置、街道之间的距离以及接入点的数量，请帮助当地政府确定所能达到的最小平方距离和。

输入格式

输入包含三行。第一行包含四个整数 $m, n, k, s$，其中 $m$ 和 $n$ ($1 \le m, n \le 1\,000$) 分别是两条道路上客户的数量，$k$ ($1 \le k \le \min(\max(m, n), 100)$) 是要放置的接入点数量，$s$ ($1 \le s \le 50$) 是两条道路之间的距离。第二行包含 $m$ 个浮点数 $x_1, x_2, \dots, x_m$ ($0 \le x_i \le 1\,000$)，表示第一条道路上 $m$ 位客户的位置。第三行类似，包含第二条道路上 $n$ 位客户的浮点位置。第二行和第三行上的所有值各不相同（但某些值可能同时出现在两行中）。客户位置最多包含四位小数。

输出格式

输出一个浮点值，等于每位客户到最近的 $k$ 个接入点距离的平方和的最小值。答案的绝对误差或相对误差应在 $10^{-5}$ 以内。

样例

样例输入 1

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

样例输出 1

18.86666667