Lemon tree P96448

Professor Oak kas a big lemon tree that produces nice lemons. However, every time that a friend visits him, he or she always asks for “a few” of them. As a result, Prof. Oak can barely enjoy his own lemons.

Tired of this situation, Prof. Oak has decided to impose a rule: When someone asks for lemons, he or she can only take a Fibonacci number of them. (Remember the definition: F₀ = 0, F₁ = 1, F_n = F_n−1 + F_n−2 for n ≥ 2.) This way, perhaps some lemons can be saved...

The lemon tree has currently ℓ lemons, and a group of m mathematicians visits Prof. Oak. They will collaborate to take the maximum total number of lemons. (They will share all them later.) For instance, if ℓ = 46 and m = 2, then each mathematician can ask for F₈ = 21 lemons, only leaving 4 lemons to Prof. Oak. It is easy to see that there is no combination for 2 mathematicians with a sum larger than 42 but not larger than 46.

Given ℓ and m, how many lemons will Prof. Oak enjoy?

Input

Input consists of several cases, each with ℓ and m. Assume 0 ≤ ℓ ≤ 10¹⁸ and 0 ≤ m ≤ 1000.

Output

For every case, print the number of lemons left by the mathematicians.