C. 检查点
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定 $$$n$$$ 个检查点，每个检查点坐标分别为 $$$p_1,p_2,\cdots,p_n$$$，Yezhka 在场地上放了 $$$m$$$ 枚棋子，其坐标为 $$$x_1,x_2,\cdots,x_m$$$。

现在 Yizhka 可以操作若干次，对于每次操作，仅能将其中一枚之前未移动过的棋子，可以移动到新的位置，移动到距离为 $$$d$$$ 的位置需要消耗 $$$d^2$$$ 的代价。

已知 Yizhka 最多能消耗 $$$k$$$ 点代价，使得所有棋子都位于检查点内。

很明显，不是每局游戏 Yizhka 都能使所有棋子到达检查点，于是他决定尝试放宽检查点判定，他可以只需要把棋子移动至检查点附近即可。

现在，他可以将所有检查点都放宽至 $$$[p_i-r,p_i+r]$$$ 的范围之中。在他可以修改检查点范围的前提下，他想知道他需要至少放宽判断范围 $$$r$$$ 才能胜利。（由于游戏存储限制，$$$r$$$ 仅可以是非负整数值）

Input

第一行输入 $$$3$$$ 个正整数 $$$n,m,k\ (1\le n,m\le 2\times 10^5,0\le k\le 10^{16})$$$。

第二行输入 $$$n$$$ 个整数 $$$p_i\ (0\le |p_i|\le 10^8)$$$，表示检查点坐标。

第三行输入 $$$m$$$ 个整数 $$$x_i\ (0\le |x_i|\le 10^8)$$$，表示每枚棋子的初始位置。

Output

共输出一行 $$$1$$$ 个非负整数，表示至少需要放宽的半径 $$$r$$$。

Examples
Input
1 3 15
10
5 9 16
Output
3
Input
12 23 998244353
12199216 90749213 -62833415 -38258866 -14446715 -35650520 -49600331 33618438 -54860314 5014791 -97029528 -23175106
-68729860 96557776 89224060 26314437 8623611 -10558853 78829390 -20209361 -62085211 -50453124 82907520 -22446844 -47205672 74576319 -130016 -78318307 -58367447 -44618411 -93888793 -80921259 39756497 292969 -69694719
Output
16141299
Note

对于第一组样例：

当 $$$r=3$$$ 时，检查点检查范围扩大至 $$$[7,13]$$$，此时，符合条件的移动方案是 $$$5\to 7,16\to 13$$$，此时需要的代价为 $$$4+9=13$$$，可以证明没有更优的方案。