B Road Band

All the residents of the rural community of Axes Point live on one of two parallel streets separated by a band of green park land. Recently, the local board of supervisors received a grant to bring wireless service to the town. The grant pays for $k$ access points, and the supervisors have decided to place them in a straight line on County Road "B," which lies in the wooded band midway between the two residential streets. They want to place them so that the distance between each user and the nearest access point is as small as possible. Specifically, they want to minimize the sum of the squares of the distances of each user from the nearest access point.

The figure shows two streets with eight customers and their locations along the streets. The streets are $3$ units apart, and two access points are placed at points midway between the two streets so that the sum of the eight squared distances is minimized.

Given the locations of all customers along each street, the distance between the streets, and the number of access points, find the minimum sum of squared distances that can be achieved.

The first line contains four integers $m$, $n$, $k$, $s$. Here $m$ and $n$ ($1 \leq m,n \leq 1000$) are the numbers of customers along each of the two roads, $k$ ($1 \leq k \leq \min(\max(m,n),100)$) is the number of access points, and $s$ ($1 \leq s \leq 50$) is the distance between the two roads.

The second line contains $m$ floating-point values $x_1, x_2, \ldots, x_m$ ($0 \leq x_i \leq 1000$), the locations of the customers along the first road. The third line contains $n$ floating-point locations of the customers along the second road. All values on each of the second and third lines are distinct, but some values may appear on both lines. Customer locations have no more than four decimal places.

Output a single floating-point value equal to the minimum sum of squared distances from each customer to the closest of the $k$ access points. An answer is accepted if its absolute or relative error is at most $10^{-5}$.