This page is still under construction.

Parts of this page are still being built. What you see may change.

Hanger Hanger Hanger

Time limit0.5sMemory limit1024 MB

Summary
Using exactly M hangers, place complete binary hanger trees of height 1, 2, or 3 at N or fewer spots to maximize the total number of bottom hanging positions.
Level

Medium7 of 10

Topics
Dynamic programming, Combinatorics, Math, Greedy
Solved
No attempts yet

Problem

You need to tidy up your closet, but there are too many clothes and they are spilling onto the closet floor. There are NN spots where you can hang a hanger, and you have MM hangers. Then you realize something remarkable: when you have more hangers than the closet can hold, hanging hangers on a hanger lets you hang more clothes!

Instead of hanging clothes on a hanger, you can hang hangers on both sides of it to hold more clothes, but to keep the hanger balanced you must build a complete binary hanger where the total number of hangers on both sides is the same. Naturally, you can hang clothes only on the bottommost hangers that have no hangers hanging from them.

Call a single hanger a hanger tree of height 1. Hanging one hanger on each side of a hanger gives a hanger tree of height 2. Repeating this, hanging a hanger tree of height ii on each side of a hanger gives a hanger tree of height i+1i+1. The closet is short, so you can hang clothes only on hanger trees of height 3 or less. A hanger tree of height 4 fits in the closet but is too tall to hang clothes below it, and a hanger tree of height 5 or more does not fit in the closet. You have nowhere else to put hangers, so you must use every hanger, and you do not need to place a hanger tree at every spot where a hanger can be hung.

Find the maximum number of clothes you can hang while placing hanger trees so that the conditions hold.

Input

The first line gives the number of spots where a hanger can be hung and the number of hangers, NN and MM. (1≤N≤5,000,1≤M≤10,0001\leq N \leq5,000, 1\leq M \leq 10,000)

Output

On the first line, print the maximum number of clothes you can hang. If there is no way to hang MM hangers at NN or fewer spots while satisfying the conditions above, print −1-1.

Hint

If you place hanger trees of heights 1, 2, 2, 3 in that order, you can hang 1, 2, 2, 4 clothes on them respectively.

Examples1

  1. Example 1

    Input
    4 14
    
    Expected output
    9