Masala M

Tog' cho'qqisidagi bosh shtabdan tog' etagidagi front chizig'igacha aloqa postlari tarmog'i o'rnatilgan. Postlar tog' yonbag'rida uchburchak shaklidagi ierarxik tuzilmada joylashgan: 

- cho'qqida yagona bosh shtab turadi (\(1\)-post);

- har bir keyingi bosqich (qator) oldingisidan bitta ko'proq postga ega;

- postlar yuqoridan pastga, har bir bosqichda chapdan o'ngga ketma-ket natural sonlar bilan raqamlangan.

Quyida \(5\) bosqichli tarmog' sxemasi keltirilgan:

 Harbiy buyruqlar bosh shtabdan quyidagi tartibda uzatiladi:
- buyruq har doim \(1\)-postdan (bosh shtab) boshlanadi;

- har bir postdan signal faqat keyingi bosqichdagi ikkita qo'shni postdan biriga — chap pastga yoki o'ng pastga — yo'naltiriladi;

- har bir post signalni kuchaytirib uzatadi, kuchaytirish darajasi shu post raqamiga teng. 

Jangning hal qiluvchi lahzasida \(K\)-postga favqulodda buyruq yetkazish lozim. Marshrutni shunday tanlash kerakki, buyruq o'tgan barcha postlar raqamlari yig'indisi eng katta bo'lsin.

Masalan, \(9\)-postga buyruq yetkazishning bir necha yo'li mavjud:

| Marshrut | Yig'indi |

| \(1 \to 3 \to 6 \to 9 | \textbf{19}\) |

| \(1 \to 2 \to 5 \to 9 | 17\) |

| \(1 \to 3 \to 5 \to 9 | 18\) |

Ko'rinib turibdiki, \(1 \to 3 \to 6 \to 9\) marshruti eng katta yig'indini beradi.

Standart kirish oqimining birinchi qatorida \(K\) natural soni berilgan — buyruq yetkazilishi lozim bo'lgan post raqami. \((1\le K \le 10^9)\)

Standart chiqish oqimiga yagona qatorda \(K\)-postga olib keladigan marshrut bo'yicha postlar raqamlari yig'indisining eng katta qiymatini yozing.