P7514 [NOI Qualifier Joint Contest 2021 A/B Paper] Card Game.

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.

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

Only one line, an integer, indicating the answer.

**[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: | Test Point ID | $n \le$ | Special Constraint | |:-:|:-:|:-:| | $1 \sim 2$ | $10$ | None. | | $3 \sim 4$ | $500$ | None. | | $5 \sim 6$ | $5 \times {10}^5$ | $m \le 1000$. | | $7$ | ${10}^5$ | None. | | $8$ | $4 \times {10}^5$ | None. | | $9$ | $7 \times {10}^5$ | None. | | $10$ | ${10}^6$ | None. | Translated by ChatGPT 5