Lemon tree P96448


Statement
 

pdf   zip

thehtml

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: F0 = 0, F1 = 1, Fn = Fn−1 + Fn−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 F8 = 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 ≤ ℓ ≤ 1018 and 0 ≤ m ≤ 1000.

Output

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

Public test cases
  • Input

    46 2
    4 1000
    679891637638612257 1
    

    Output

    4
    0
    259695496911122584
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++ Java