g5-09153. 预算选点 未做

海岸线自西向东有 $n$ 个候选点位,第 $i$ 个点位位于坐标 $x_i$($x_i$ 互不相同),在点位建瞭望塔的代价为 $c_i$。地基条件自西向东越来越差,代价沿坐标不减:把点位按坐标排序后 $c$ 构成不减序列。要在预算 $B$ 之内建至少 $k$ 座塔,且任意相邻两塔的间距不小于 $d$。请求出最大的可行 $d$。数据保证按坐标排序后前 $k$ 个点位的代价总和不超过 $B$,故 $d=0$ 一定可行,答案存在。

第一行三个整数 $n,k,B$。
接下来 $n$ 行,每行两个整数 $x_i,c_i$,顺序任意。

一行一个整数,表示最大的可行 $d$。

按坐标排序后为 $(1,1),(3,2),(6,2),(7,5),(12,9)$,代价已不减。试 $3$:间距不小于 $3$ 的三点组合里,最省的是 $1,6,12$,代价 $1+2+9=12>10$,其余组合更贵,不可行。试 $2$:选 $1,3,6$,代价 $1+2+2=5$,间距 $2,3$,可行。故答案为 $2$。

$1\le k\le n\le 10^5$;$0\le x_i\le 10^9$ 且互不相同;$1\le c_i\le 10^9$ 且按坐标排序后不减;${\sum }_{i=1}^k{c}_i\le B\le 10^{18}$(排序后求和)。