Zadanie

Ingrediencie, traste sa

Počet bodov: 70

Na chate KSP nastala veľká kríza. Vedúci sú hladní. No a ako vyriešia tento problém? Predsa zorganizujú hlasovanie. Dlho hlasovali, padal jeden návrh za druhým, ale stále sa nevedeli zhodnúť. V tom to Krta prestalo baviť a vyhlásil:

“Načo budeme chodiť do nejakého Macdonaldu, či iných fastfoodov, keď mám zo sebou moju masívnu mačetu? Ňou jednoducho pripravím ľubovoľný pokrm¹.”

A tak sa zobral aj so svojou mačetou a začal si pripravovať ingrediencie.

Úloha

Krto svojou mačetou seká ingrediencie veľmi zaujímavým spôsobom. Ak je dĺžka ingrediencie párna, rozsekne ju na polovicu a jednu časť odhodí. Ak je dĺžka nepárna, odsekne z konca \(1\) cm a vyhodí ho. Teda z ingredience dlhej \(x\) sa stane ingrediencia dlhá:

• \(\frac{x}{2}\), ak je \(x\) párne
• \(x-1\), ak je \(x\) nepárne

Na navarenie pokrmu potrebuje Krto mačetou nakrájať aspoň \(k\) kusov ingrediencií, všetky rovnakej dĺžky. K dispozícií má ingrediencie dĺžok \(1\) až \(n\), z každej dĺžky jednu. Akú najväčšiu dĺžku ingrediencií môže vybrať, aby zvládol navariť pokrm?

Vstup a Výstup

Jediný riadok vstupu obsahuje \(2\) čísla \(n\) a \(k\) \((1 \leq k \leq n \leq 10^{18})\), celkový počet ingrediencií a počet ingrediencií potrebných na navarenie pokrmu.

Na výstup vypíšte jedno číslo, najdlhšiu možnú dĺžku, na ktorú vie Krto mačetou nakrájať aspoň \(k\) ingrediencií. Dá sa dokázať, že takáto dĺžka za daných podmienok vždy existuje.

Bodovanie pre testovacie sady: - Sada 1 (20 bodov): \(n \leq 10^{6}\) - Sada 2 (20 bodov): \(n \leq 10^{9}\) - Sada 3 (15 bodov): \(n \leq 10^{18}\) - Sada 4 (15 bodov): \(n \leq 10^{18}\)

Príklad

Input:

11 3

Output:

5

Na dĺžku \(5\) dokáže nakrájať suroviny \(5\), \(10\) a \(11\). Pre väčšie dĺžky vie nakrájať najviac \(2\) kusy ingrediencií.

Input:

11 6

Output:

4

Na dĺžku \(4\) dokáže nakrájať suroviny \(4\), \(5\), \(8\), \(9\), \(10\) a \(11\). Napríklad surovinu \(11\) nakrája \(11 \to 10 \to 5 \to 4\).

Input:

20 20

Output:

1

Každú surovinu dokáže nakrájať na dĺžku \(1\).