Dishonest Sellers · Interview Problem

Back to problems

Codeforces

Medium

Arrays

Sorting

Greedy

Dishonest Sellers

Buy exactly $k$ items at their first-price or second-price values so that the total cost is minimum.

Acceptance 0%

Start Practice

Problem Statement

You are given $n$ items. For each item $i$ , there are two possible prices: a normal price $a_i$ and a discounted price $b_i$ . You must buy exactly $k$ items at the normal price and all remaining items at the discounted price.

Your task is to choose which $k$ items to buy at the normal price so that the total amount paid is as small as possible.

Input Format

Input

The first line contains two integers $n$ and $k$ .
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ .
The third line contains $n$ integers $b_1, b_2, \dots, b_n$ .

Interpretation

Item $i$ costs $a_i$ if bought at the normal price.
Item $i$ costs $b_i$ if bought at the discounted price.
Exactly $k$ items must be purchased at the normal price.

Output Format

Output

Print one integer: the minimum total cost achievable.

Constraints

$1 \le k \le n$
Values are integers and may be large enough that a 64-bit integer is needed for the answer.

Examples

Sample cases returned by the problem API.

Example 1

Input

3 1
10 20 30
5 10 25

Output

Explanation

If item 1 is bought at the normal price, the total is $10 + 10 + 25 = 45$ . Choosing item 2 or 3 instead gives a larger total.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress