CONTEXT

. The price_dict is the ingredient menu

The bun "B" is free (i.e., $0).

All the prices for each individual ingredient are in integer (int) dollar (i.e., $).

We will give you the ingredients in a dictionary excluding the bun.

- If "C" stands for cheese, "V" stands for vegetables, "P" stands for patty and "A" stands for abalone slices then the prices will be given as dictionary: {"C": 1, "V": 3, "P": 11, "A": 31}

- The ingredients may be arranged in any order. You may not assumed that the dictionary given is sorted.

- For every price $p -except for the most expensive price- the next more expensive price is at least double of $p. For instance, in the example price list above, the price for "V" is $3 and the next more expensive price is "P" at $11. Note that 11 >= 2 + 3.

Each ingredient can only appear at most in each burger except the bun. In other words, you cannot have a burger "BPCCB" because "C" appears more than once.

The burger will only be sandwiched by exactly two pieces of buns: one at the start and one at the end. In other words, you cannot have a burger "BPBCB" because there is an additional "B" in the middle.

QNS

One day, your customer comes with exactly $m of money. The customer asks you to find him the most expensive burger you can buy from our Caf. As a programmer, you code a quick program to answer this, returning a tuple (tuple) (burger, change) which is a pair of burger (str) satisfying our representation of burger and the amount of money left after paying for the burger. Note that if the customer cannot afford any ingredient, then they don't even get the bun. For maximum taste, the most expensive ingredient should be placed on the topmost part of the burger inside the buns. In our representation, this means that the most expensive ingredient is on the leftmost part of the burger in between the two "B". For instance, given the price list from before, we can have "BAPVCB" but not "BCVPAB".

Question

Write the function most_expensive_burger(money, price_dict) that takes in the money money (int) and the price list price_dict (dict) find the pair of burger (str) and the amount of money left (int) after paying the burger satisfying the criteria above.

Restrictions

You are not allowed to modify the input dictionary.

RULES:

• You must pass all test cases
• You must pass all hidden secret test cases ( can you guess what they are???)

Assumptions

money >= 0

Hint

You can be greedy in your construction of the burger. Try to include the most expensive ingredient first into your output burger.

SAMPLE RUNS

def most_expensive_burger(money,price_dict): pass price_list={"C":1,"V":3,"P":11,"A":31} 

>>> most_expensive_burger(0, {"C": 1, "V": 3, "P": 11, "A": 31}) ('', 0) 

>>> most_expensive_burger(25, {"C": 1, "V": 3, "P": 11, "A": 31}) ('BPVCB', 10) 

>>> most_expensive_burger(55, {'C':1,'W':2,'I':4,'T':9,'O':20,'V':41,'S':85}) ('BVTICB', 0)