There is a huge garden in the city. The Garden contains n numbers of flowers. James has arrived in that city to buy exactly k flowers. He then went to the owner of this garden to discuss the prices of flowers. The owner of the garden provides James with an array âcostâ of n numbers which denotes the prices of the flower, the price of ith flower is cost[i].
Since today is the Birthday of Garden Owner , so he has provides a discount which is given by 2D array âdiscountâ, where 1st column represents x and second column represent y. It represents that on buying any x flowers from the n flowers, the yth cheapest flower from that x flowers is free.
Let's say we have flowers with cost [1, 1, 3, 4] then for x=3 and y=2, if we pick any three flowers say [1, 3, 4], then second cheapest flower that is flower with cost 3 is free and you have to pay only first and third flower i.e. 1+4=5.
Also other way is, if you pick [1, 1, 3] then the second cheapest flower that is flower with cost '1' will be free and you will pay only for the cost of first and third flower i.e. 1+3=4.
Since James has other plans as well, he wants to save money. So he has asked you to buy exactly k flowers with the minimum cost possible.
Input : n = 5, m = 2, k = 4, cost = [2, 3, 1, 5, 4], discount = [ [2, 1], [3, 2] ]
Output : 6
Explanation : First James will buy 2 flowers of cost 1 and 2 and using 1st discount he will get both flowers in just 2 Rs.
Then James will buy 2 more flowers of cost 3 and 4 and using 1st discount he will get both flowers in just 4 Rs.
So total cost = 2 + 4 = 6.
Input : n = 5, m = 2, k = 3, cost = [100, 100, 100, 100, 100], discount = [ [2, 1], [3, 3] ]
Output : 200
Explanation : First James will buy 2 flowers of cost 100 and 100 and using 1st discount he will get both flowers in just 100 Rs.
Then james will buy 3rd flower of cost 100 and now there is no discount on buying 1 flower, so he will get 3rd flower in 100Rs.
So total cost = 100 + 100 = 6.
Input : n = 6, m = 4, k = 4, cost = [9, 3, 7, 2, 10, 1], discount = [ [2, 2], [3, 3], [4, 4], [5, 5] ]