Description

Alice has $n$ cards. On the front of the $i$-th card ($1 \le i \le n$) there is a number $a_i$, and on the back there is a number $b_i$. Initially, all cards are face up.

Now Alice may flip at most $m$ cards, changing them from face up to face down. Alice’s goal is to make the range (the difference between the maximum and minimum) of the $n$ numbers showing in the end as small as possible. Please help Alice compute the minimum possible range.

Input Format

The first line contains two positive integers $n, m$, representing the number of cards and the maximum number of cards that may be flipped.
The second line contains $n$ positive integers; the $i$-th number is $a_i$.
The third line contains $n$ positive integers; the $i$-th number is $b_i$.

The testdata guarantees that all $2 n$ numbers on the cards are pairwise distinct, and the cards are given in increasing order of $a_i$.

Output Format

Only one line, an integer, indicating the answer.

6 3
8 11 13 14 16 19
10 18 2 3 6 7

8

见附件中的 card/card2.in。

见附件中的 card/card2.ans。

见附件中的 card/card3.in。

见附件中的 card/card3.ans。

Hint

[Sample #1 Explanation]

One optimal plan: flip cards $1, 5, 6$. The numbers showing in the end are, in order, $10, 11, 13, 14, 6, 7$, and the range is $14 - 6 = 8$.

[Constraints]

For all testdata: $3 \le n \le {10}^6$, $1 \le m < n$, $1 \le a_i, b_i \le {10}^9$.

The specific limits for each test point are shown in the table below:

Translated by ChatGPT 5