FastPrepFastPrep
Problem Brief

Fortune Telling 🍒

OA
See Amazon online assessment and hiring insights

Given a collection of n cards. The i-th card (1 ≤ i ≤ n) has a number Ai on its front and a number Bi on its back. At the start, all the cards are facing upwards. He wants to minimize the range of numbers (i.e. the difference between the maximum and minimum values) on the face-up side. He is allowed to flip a maximum of m cards. Flipping a card will transition Bi to the face up side and Ai to the back. Help him find the minimum possible range after using at most m flips.

Input

The first line of the input consists of 2 integers n and m. The next line contains n integers, i-th of which denotes Ai. The next line contains n integers, i-th of which denotes Bi.

Output

Output a single integer, the minimum possible range.

1Example 1

Input
n = 5, m = 2, A = [1, 2, 17, 16, 9], B = [3, 4, 5, 6, 11]
Output
8
Explanation
By flipping card 3 and 4, we get the face up numbers {1, 2, 5, 6, 9}. This makes range=9-1=8.

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= m <= n
  • 1 <= Ai, Bi <= 107
    • public int minimizeTheRange(int n, int m, int[] A, int[] B) {
  // write your code here
}
    Input

    n

    5

    m

    2

    A

    [1, 2, 17, 16, 9]

    B

    [3, 4, 5, 6, 11]

    Output

    8

    Sign in to submit your solution.