fibosir

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:

• $F_1 = 1$
• $F_2 = 1$
• $F_N = F_{N-1} + F_{N-2}$

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

Cerinţă

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 $K$ secvenţe disjuncte de lungime $K$ din $fibosir(N)$.

Restricții și precizări

• $0 < N \leq 2 \ 000$
• $0 < M \cdot 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

$fibosir(8)$: $1123581321$ sunt eliminate $3$ secvențe de lungime $2$: $11$, $23$, $13$