$S(n)$ функцээр $n$ тооны аравтын бичлэг дахь цифрийн тоог олдог гэе. Жишээ нь $S(893)=3$, $S(114514)=6$.

Та $m$ тоонос эхэлсэн дараалсан элементтэй дараалал ($m$, $m+1$, ...)-г үүсгэхийг хүсч байгаа. Тэгэхдээ та дараалалд $n$ тоог нэмэхийг тулд $S(n)·k$ төлбөр төлөх хэргтэй.

Та хамгийн ихдээ $w$ хэмжэний зардал гаргаж болох бөгөөд, хамгийн урт дараалал үүсгэхийг хүссэн юм. Үүсгэж болох хамгийн урт дараалын уртыг олдог програм зохионо уу.

Оролт

Оролтын эхний мөрөнд $w$ ($1 ≤ w ≤10^{16}$), $m$ ($1 ≤ m ≤ 10^{16}$), $k$ ($1 ≤ k ≤ 10^9$) өгөгдөнө.

Жич: C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Гаралт

Бодлогын хариу болох ганц тоог хэвлэнэ.