# Help me in solving Minimum total cost to pay

• I have a minimum card balance required to visit a club.You should balance equal or more than that.
• Once you visit a club you need to pay some cost. What is the minimum card balance to visit all clubs ?

|Minimum card balance|11|6|5|7|
|Cost Occured                 | 3|4|2|1|

The answer for this questions is 12. I visit (11,3) → ->(7,1)->->(5,2)->

If i have 500000 such pairs how do i go about solving this problem ? I looking at less than O(N^2) more like O(nlogn) I thought about generating all permutations but it is possible for only less than 10 pairs.

I tried sorting by decreasing order of minimum card balance. (11,3),(7,1),(6,4),(5,2).

• Lets take the minimum cost is 11. Then 11->(11,3)->->(7,1)->->(6,3)->-X not sufficient to buy (5,2). Lets take the minimum cost is 12.Then in the order 12->(11,3)->->(7,1)->->(6,4)-> X
• The order of pairs matter.Even though 12 is a valid solution the order in he visits the club matter.

So i have to try n! ways of visits to club and check the minimum cost one by one which doesn’t solve the problem for 500000 pairs

I also tried sorting by cost occured. 12->(7,1)->->(5,2)->-X Can’t satisfy (11,3).