Store Art

Charlie est un grand fan d'art contemporain. Il serait bien devenu artiste, mais comme il faut bien manger, il s'est fait PDG de multinationale. Ça paye mieux, et puis il a la chance de travailler dans un immense building couvert de fenêtres à stores individuels.

Tous les matins, il dessine un monochrome sur une façade du building, en levant ou baissant les stores des fenêtres. Comme un dessin peut utiliser beaucoup de stores, le PDG actionne seulement le store de son bureau et met à contribution ses employés pour les autres stores, en leur indiquant par téléphone le dessin à réaliser.

Chaque employé reçoit donc un coup de téléphone, prend connaissance du dessin du jour, actionne son store en fonction du dessin, puis peut téléphoner à son tour à d'autres employés. Il faut savoir que le PDG est moins moderne que son art, et n'a pas installé de réseau intranet dans son entreprise : un employé doit obligatoirement être appelé par le PDG ou par un autre employé avant d'actionner son store, car c'est le seul moyen de connaître le dessin du jour choisi par le PDG.

Actionner un store est instantané, mais chaque appel téléphonique dure 1 minute. Une personne ne peut être au téléphone qu'avec une seule autre personne à la fois. Le PDG et les employés sont très organisés, ils s'arrangent toujours pour n'appeler que les employés qui ne connaissent pas encore le dessin du jour, et qui n'ont donc pas encore actionné leur store. Pour éviter de déranger trop longtemps les employés, le PDG a fixé une limite au nombre de coups de téléphone que peut émettre chaque employé. Le PDG est également concerné par la limite.

Prenons un petit exemple. Au temps 0 minute, le PDG actionne son store, puis peut décider de téléphoner à un employé. Au temps 1 minute, 2 stores sont actionnés. Le PDG peut appeler un autre employé, et le premier employé peut lui aussi appeler un autre employé : au temps 2 minutes, 4 stores sont actionnés. Si la limite du nombre d'appels par personne est égale à 2, le PDG ne peut plus appeler, mais les 3 employés déjà contactés le peuvent.

L'objectif est de trouver le temps minimal nécessaire pour réaliser le dessin, c'est-à-dire pour que tous les stores soient actionnés en fonction du dessin du jour.

• 0 <= N <= 500 000 000, où N est le nombre de stores à actionner.
• 2 <= K <= 1000, où K est le nombre maximum de personnes que peut appeler au téléphone chaque personne pour réaliser l'œuvre d'art du jour. La limite concerne PDG et employés.

De plus, dans 35% des tests d'entrée, N <= 10 000.

• La première ligne de l'entrée contient l'entier N.
• La deuxième ligne de l'entrée contient l'entier K.

Vous devez écrire un seul entier sur la sortie : le temps minimum nécessaire pour actionner tous les stores, en minutes.