Maximum Sum of Products

Given two arrays of integers, ( nums1 ) and ( nums2 ) of length ( n ), and an integer ( k ), you are allowed to reorder ( nums1 ) arbitrarily while the order of ( nums2 ) must remain unchanged. You need to select exactly ( k ) pairs where each pair is formed by pairing an element from the reordered ( nums1 ) with the corresponding element from ( nums2 ).

The objective is to maximize the sum of the products of these ( k ) pairs. In mathematical notation, if you assign a permutation ( p ) to ( nums1 ), and choose a subset ( S \subseteq {0, 1, \ldots, n-1} ) such that ( |S| = k ), then you want to maximize: [ \sum_{i \in S} p[i] \times nums2[i] ]

It is guaranteed that ( n \ge k ) and all numbers in the arrays are positive.

inputFormat

The first line of input contains two integers ( n ) and ( k ) where ( n ) is the number of elements in each array and ( k ) is the number of pairs to select. The second line contains ( n ) space-separated integers representing ( nums1 ), and the third line contains ( n ) space-separated integers representing ( nums2 ).

outputFormat

Output a single integer representing the maximum sum of the products of the selected ( k ) pairs.## sample

3 2
1 3 2
4 5 1

23