Description

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.

Input Format

$$\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.

Output Format

$$\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.

4 3
1 2 3 1 4 1 6 1

3

5 2
1 0 15 0 4 0 10 0 6 0

5

Hint

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.