For a new statistic, span-relation, for two arrays of integers, arr1 ,and arr2 is the product of the minimum of the arr1 and the sum of the arr2. For example, the span relation of [2,4,3,5] and [1,2,3,4] is 2x(1+2+3+4) = 20.
Given two arrays(as list in java) arr1 and arr2 of n integers each and an integer k, choose exactly k indices i1, i2, ..., ik such that the span-relation of the sets [arr1[i1], arr1[i2], ..., arr1[ik] and arr2[i1], arr2[i2], ..., arr2[ik] is maximum.
Return the maximum possible span-relation.
Example1:
Given n=4, k=3, arr1=[2,1,3,4] and arr2=[1,3,3,2].
Output: 12
Explanation: One optimal selection of k indices is 0,2 and 3. The sets formed are [2,3,4] and [1,3,2] giving a maximum span-relation of 2x(1+3+2) = 12.
Example2:
Given n=8, k=4, arr1=[7,9,17,7,8,5,12,4] and arr2=[13,10,7,1,3,12,15,5].
Output: 315
Explanation: Optimal way to choose the k indices is 0,1,2 and 6 giving the sets [7,9,17,12] and [13,10,7,15] giving the maximum span-relation of 7x(13+10+7+15) = 315.
Example3:
Given n=5, k=1, arr1=[7,5,10,9,6] and arr2=[4,2,3,1,1].
Output: 30
Function Description:
Complete the function getMaxSpanRelation, which has the following parameters(s)
int arr1[n]: an array of n integers.
int arr2[n]: an array of n integers.
int k: the number of indices to choose
Return:
long int: the maximum possible span-relation.
Constraints:
1 <= n <= 10^5
1 <= k <= n
0 <= arr1[i] <= 5000
0 <= arr2[i] <= 5000