题号：NC219931
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
我猜你一定见过这题。
有两座城市，不妨称作 
城和 
城。
你有 
个信号站，每个信号站都有相同的整数通信半径 
，也就是说一座在坐标 
的信号站能覆盖闭区间 
。两个信号站都在对方的通信区间内则称两个信号站之间有连接，当然如同字面意思，连接具有传递性，即如果 
号信号站和 
号信号站直接连接， 号信号站与 
号信号站直接连接，那么 号信号站也与 号信号站连接。
特殊地，若城市落在了某个信号站的通信区间内，称该城市与该信号站之间有连接。
现在你可以移动一些信号站的位置(当然也可以不移动，也可以重复移动同个信号站)，把 个信号站往左或往右移动 单位距离的代价是 。注意，移动的最小单位是 ，也就是说你只能移动整数倍单位距离。
问在总代价不超过 的情况下，通信半径
最少能有多小，使得
城与
城之间有连接。
输入描述:
第一行三个整数。
第二行
，表示第
个信号站在坐标轴上的位置。
输出描述:
输出一个整数，表示可能的最小半径。
