Problem Description

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

Alice can flip at most $m$ cards, changing them from face up to face down. Alice's goal is to minimize the range (the difference between the maximum and minimum values) of the $n$ numbers that are face up. Help Alice calculate the minimum range.

Input Format

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

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

Output Format

A single line containing one integer, representing the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

8

Sample Input #2

See the attached file card/card2.in.

Sample Output #2

See the attached file card/card2.ans.

Sample Input #3

See the attached file card/card3.in.

Sample Output #3

See the attached file card/card3.ans.

Notes

[Sample #1 Explanation]

One of the optimal solutions: Flip the $1st, 5th, and 6th$ cards, resulting in the numbers facing up being $10, 11, 13, 14, 6, 7$, with a range of $14 - 6 = 8$.

[Data Range]

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

Specific restrictions for each test point are as follows:

见题面 Input 部分

见题面 Output 部分