Detective’s Team
The Covid-19 pandemic is raging worldwide, and almost the whole world is under lockdown.
Many countries blame China for the pandemic and India is one of them, but China is not
accepting it and is also hiding much crucial information about the virus.
Indian Government decided to send a Team of ‘K’ elite Detectives to China for a hidden
investigation. The government approached Agency X for the Detectives. All the Detectives in
Agency X are pros, but they each have different skill levels and each detective is independent to
demand different amounts for the work. This amount is the minimum amount for which they
would be ready to work( if the government offered less pay then they would reject the offer, but
a higher pay is valid).
Agency X has a total of N independent detectives under them. The Agency X follow certain
rules for the payment to the detectives:
- Every Detective should be paid in the ratio for their skill corresponding to the other
detective’s skills in the team of K people. - Every Detective should be paid at least the amount demanded by him/her.
Since the whole country is in lockdown and it is leading to a recession in the country, So the
government would like to expand the minimum amount in forming a Team of K Detectives.
Input
It consists of three lines:
Line 1 contains two integers N, K. ‘N’ is the number of Detectives in Agency X. ‘K’ is the size
of the Team of Detectives to be formed.
Line 2 contains n integers s1, s2, s3, . . . . , sn, where si represents the skill of the detective i.
Line 3 contains n integers d1, d2, d3, . . . . . , dn, where di is the amount demanded by detective i.
Output
Print the minimum amount of money required to be paid by the Indian Government to the
Agency X, for forming a team of K detectives.
Answers should be ceil of the actual of the answer to be considered correct.
Sample Input 1
3 2
10 20 5
70 50 30
Sample Output 1
105
Sample Input 2
5 3
3 1 10 10 1
4 8 2 2 7
Sample output 2
31
Note- ceil(30.6667) = 31
Explanation: - We pay 70 to 0-th worker and 35 to 2-th worker.
- We pay 4 to 0-th worker and 13.3333 to 2-th and 3-th workers each.
Grading. - (4) 1 <= K <= N <= 1000
- (6) 1 <= K <= N <= 100000