You have two baskets with n fruits each. basket1[i] and basket2[i] are the costs of the fruits in them. You want the two baskets to be equal: once both are sorted by cost, they must be exactly the same array.
To get there, you may repeat the following move as many times as you like:
- Pick an index
iinbasket1and an indexjinbasket2, and swap those two fruits. - The swap costs
min(basket1[i], basket2[j]).
Return the minimum total cost to make the baskets equal, or -1 if it can't be done.
The answer can be larger than 2^31 − 1, so use a 64-bit integer (
long/long long) in Java, C++ and C.
Examples
Example 1
Input: basket1 = [3,3,8,8], basket2 = [1,1,8,8]
Output: 1
Swap a 3 from basket1 with a 1 from basket2 for min(3, 1) = 1. Both baskets become [1,3,8,8] once sorted.
Example 2
Input: basket1 = [1,2], basket2 = [2,3]
Output: -1
There's only one fruit costing 1, so it can never be in both baskets.
Example 3
Input: basket1 = [10,10,10,10], basket2 = [20,20,20,20]
Output: 20
Swap a 10 with a 20 twice, paying 10 each time.
Example 4
Input: basket1 = [1,10,10,10,10], basket2 = [1,20,20,20,20]
Output: 4
Swapping a 10 and a 20 directly costs 10. It's cheaper to go through the 1s: swap basket1's 1 with a 20 (cost 1), then swap a 10 with basket2's 1 (cost 1). That moves one 10 and one 20 for a cost of 2. Doing it twice costs 4.
Example 5
Input: basket1 = [2,1], basket2 = [1,2]
Output: 0
Sorted, both baskets are already [1,2].
Constraints
basket1.length == basket2.length1 <= basket1.length <= 10^51 <= basket1[i], basket2[i] <= 10^9