Prin fibosir(N) înţelegem un şir construit prin adăugarea la sfârşit (concatenare) a primilor N termeni nenuli ai şirul Fibonacci definit astfel:

• F1=1
• F2=1
• FN = FN-1 + FN-2

De exemplu, dacă N=8 fibosir-ul construit este: fibosir(8)=1123581321.

Cerința

Pentru N valoare naturală dată, să se elimine din fibosir-ul construit M secvenţe disjuncte de lungime K fiecare, astfel încât numărul format din cifrele rămase în fiboşir să fie maxim.

Date de intrare

Fișierul de intrare fibosir.in conține pe prima linie trei numere naturale N, M şi K separate prin câte un spaţiu cu semnificaţia din enunţ.

Date de ieșire

Fișierul de ieșire fibosir.out va conține pe prima linie numărul maxim ce se obţine prin eliminarea a M secvenţe disjuncte de lungime K din fibosir(N).

Restricții și precizări

• 0 < N ≤ 2000
• 0 < M*K < lungimea fibosir(N)
• Prin secvență de lungime K înțelegem un subșir de K cifre aflate pe poziţii consecutive în șir.

Exemplu:

fibosir.in

8 3 2

fibosir.out

5821

Explicație

fiboşir(8): 1123581321
Sunt eliminate 3 secvențe de lungime 2: 11, 23, 13