DreamGrid's Luxury Shopping

3

4 votes
Greedy algorithm, Algorithms, Arrays, Greedy Algorithms, Basics of Greedy Algorithms
Problem

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:

  • He meticulously inspected all n items in the store, starting from the 1st item and ending with the nth item.
  • Whenever he checked an item, he only made a purchase if he had enough funds to cover its price. If his available funds were sufficient, he bought the item and subtracted its cost from his total wealth.
  • If, at any point, his remaining funds were insufficient to buy the item being considered, he would simply skip that particular item.

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

  • The first line consists of two integers n and m, separated by a space. Here, ndenotes the total number of luxury items available in the boutique, and m represents the number of items DreamGrid eventually purchased.
  • The next n lines each contains one integer pricei indicates the price of the ith luxury item.

Output format

Print the maximum amount of money DreamGrid needs to purchase m items in a new line.

Constraints

1n1050m<n1pricei109

 

Sample Input
4 2
1
2
4
8
Sample Output
6
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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:

  • He checks the first item with a price of 1. He buys that item since he has brought two items and the price of this item is minimum.
  • He moves on to the second item with a price of 2. he buys it. Current Wealth: 1 + 2 = 3.
  • He skips the 3rd, 4th item as well because he don't have enough wealth.
  • So he buys 2 items.

So DreamGrid's wealth is 6 and he is able to buy 2 items, which is the expected output for this test case.

Editor Image

?