Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2861
Food combination

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Only KFC has so much tasty chicken!

There are many kinds of food you can choose, such as Popcorn Chicken, Honey BBQ, BLT Salad, and KFC Snacker. You can also find many other "Individual Side Items" like Cole Slaw and so on. Of cause, there is no customer who wants to buy one kind of food twice.

The food's pricing system is very sophisticated. But we just simplify it.

Kind of food    1   2   3   4   5   6   7   8   9   10  ......
Price           1   2   4   8   16  32  64  128 256 512 ......

No one can eat out too much food. So people will buy at most L kinds of foods. And there are N kinds of foods can be chosen.

Often, people don't want to say "I need Popcorn Chicken, Honey BBQ, BLT Salad, and Bundt Cake for Desserts...". Instead, they want to know the M-th inexpensive combination of the foods can be chosen.

Your job is to calculate how much money the customer will pay when they said "I want the M-th combination".

Of cause, empty choosing is also a kind of combination, the price is zero, and it is the first inexpensive combination.


The input file contains multiple test cases.

Each test case contains three integers: N (1<=N<=31), L (1<=L<=N), M. Assume that there is a combination whose price is M-th high.

There is a blank line between test cases.

Proceed to the end of the file.


For each test case, output the price of M-th inexpensive combination.

Sample Input:

5 3 19

Sample Output:


Author: CHEN, Zhengguang
Source: ZOJ Monthly, June 2007
Submit    Status