Problem Brief

Maximize Capped Contribution Sum

FULLTIMENEW GRADOA

You are given two integer arrays a and b of the same length and an integer k. For each index i, that index contributes min(a[i], b[i]) to a total sum.

You may choose at most k distinct indices. For each chosen index, replace b[i] with 2 * b[i]. After applying those changes, the contribution of that index becomes min(a[i], 2 * b[i]).

Return the maximum possible total contribution.

Function Description

Complete the function maximizeCappedContributionSum in the editor below.

maximizeCappedContributionSum has the following parameters:

int[] a: the first array
int[] b: the second array
int k: the maximum number of indices whose b[i] value can be doubled

Returns

long: the maximum possible total sum.

1Example 1

Input

a = [5, 8, 4], b = [3, 6, 10], k = 1

Output

Explanation

The initial contribution is min(5,3) + min(8,6) + min(4,10) = 3 + 6 + 4 = 13. If you double b[0], the first contribution becomes min(5,6) = 5. If you double b[1], the second becomes min(8,12) = 8. Either choice gives a gain of 2, so the best total is 15.

2Example 2

Input

a = [10, 7, 6, 4], b = [2, 5, 4, 3], k = 2

Output

Explanation

The initial total is 2 + 5 + 4 + 3 = 14. Doubling index 0 changes its contribution to min(10,4)=4, a gain of 2. Doubling index 1 changes its contribution to min(7,10)=7, a gain of 2. Doubling index 2 changes its contribution to min(6,8)=6, a gain of 2. Any two of those three gains produce the maximum total 14 + 2 + 2 = 18.

Constraints

Limits and guarantees your solution can rely on.

The source thread did not provide explicit numeric bounds.

a.length == b.length
0 <= k <= a.length
Each index may be doubled at most once.