P15237 [NHSPC 2025] Post Office

There are $n$ towns located on a straight road. The coordinate of the $i$-th town is $x_i$. The distance between two towns is defined as the absolute difference of their coordinates. It is planned to set up post offices in $k$ towns. After the post offices are built, some of them may be temporarily closed. The goal is to make the distance from every town to the nearest operating post office as small as possible. Specifically, for the residents of the $i$-th town, their "safety tolerance" is an integer $s_i$. No matter which $s_i$ post offices are closed, they still want to be able to go to some operating post office nearby. Let $d_i$ be the distance from this town to the nearest operating post office in the worst-case scenario where at most $s_i$ post offices are closed. Our objective is to minimize the maximum $d_i$ among all towns.

$$ \begin{aligned} & n\ \ k \\ & x_1\ \ s_1\ \ \dots\ \ x_n\ \ s_n \end{aligned} $$ * $n$ is the number of towns. * $k$ is the number of post offices to be built. * $x_i$ and $s_i$ are the coordinate and safety tolerance of the $i$-th town, respectively.

$$ \begin{aligned} a \end{aligned} $$ * $a$ is the minimum possible value of $\max_{1 \leq i \leq n} d_i$ under the optimal construction plan.

### Constraints * $2 \le n \le 10^6$. * $1 \le k \le n$. * $0 \le s_i < k$. * $1 \le x_i \le 10^9$. * All input values are integers. ### Scoring This problem consists of five subtasks with the following additional constraints. Each subtask may contain one or more test cases. You must solve all test cases in a subtask to receive its score. | Subtask | Score | Additional Constraints | | :------: | :----: | ---------------------- | | 1 | 4 | $n \le 1000$, $k = 1$. | | 2 | 19 | $n \le 1000$. | | 3 | 17 | $n \le 10^5$, $x_i \le 10^6$, $s_i = 0$. | | 4 | 33 | $n \le 10^5$, $x_i \le 10^6$. | | 5 | 27 | No additional constraints. |