Minimizing Card Range

Alice has n cards. For the i-th card (1 ≤ i ≤ n), the front side displays the integer \(a_i\) and the back side displays \(b_i\). Initially, all cards are placed with the front side up. Alice is allowed to flip at most m cards, which changes the visible number from \(a_i\) to \(b_i\) on the flipped cards.

The goal is to choose a set of at most m cards to flip such that the range (the difference between the maximum and minimum numbers among all n visible cards) is minimized. Find and output the minimum possible range.

inputFormat

The input consists of three lines:

• The first line contains two integers \(n\) and \(m\) separated by a space.
• The second line contains \(n\) integers: \(a_1, a_2, ..., a_n\) representing the numbers on the front side.
• The third line contains \(n\) integers: \(b_1, b_2, ..., b_n\) representing the numbers on the back side.

outputFormat

Output a single integer representing the minimum possible range (i.e. the minimum difference between the maximum and minimum visible numbers after at most \(m\) flips).

sample

3 1
1 5 4
3 2 6

2