DreamGrid recently went on a shopping spree for luxury items at an exclusive boutique. In this boutique, there were n distinct items to choose from. DreamGrid, known for his ample wealth, employed an interesting shopping strategy:
Your task is to determine the maximum possible amount of wealth DreamGrid had at the beginning such that he can acquire some of these luxury items. You are provided with the prices of the n items and the total number of items DreamGrid ultimately purchased (indicated as m).
Your objective is to find out DreamGrid's maximum wealth that DreamGrid has before this extravagant shopping spree such that he can purchase m luxury items, which will be a non-negative whole number.
Input format
Output format
Print the maximum amount of money DreamGrid needs to purchase m items in a new line.
Constraints
1≤n≤1050≤m<n1≤pricei≤109
DreamGrid's goal is to maximize the amount of wealth he should have for purchasing m luxury items according to his strategy. Here's how the calculation is done for this test case:
So DreamGrid's wealth is 6 and he is able to buy 2 items, which is the expected output for this test case.