KiloBoom#519

KiloBoom

2 secondes
512 mégaoctets
Very hard

Vous jouez à votre jeu vidéo préféré — KiloBoom.

Dans ce jeu, vous incarnez un héros qui combat des vagues de monstres. Les monstres laissent tomber des points d'expérience après que vous les ayez vaincus, et en collectant ces points, vous pouvez augmenter le niveau de votre héros. À tout moment dans le jeu, le niveau du héros est calculé comme suit : soit le montant total de points d'expérience collectés jusqu'à présent, alors l=0 si s=0, et l = \lfloor \log_2 (s) \rfloor ^\dagger sinon. En d'autres termes, vous devez doubler vos points pour monter en niveau.

^\dagger \lfloor \log_2 (x) \rfloor est égal au plus grand entier tel que 2^k \le x. Par exemple, \lfloor \log_2 (23) \rfloor = 4, \lfloor \log_2 (8) \rfloor = 3.

Le jeu dure secondes, et après chaque seconde, les monstres que vous combattez laissent tomber l \cdot c + k points d'expérience. Ainsi, le gain d'expérience de base est de points par seconde, et avec chaque niveau supérieur, il augmente de .

Cependant, il y a un problème — votre clavier vient de se casser, et vous ne pouvez pas déplacer votre héros, et donc ne pouvez pas ramasser les points d'expérience laissés par les ennemis. Heureusement, vous avez aimants — chaque aimant, une fois activé, aspire tous les points d'expérience actuellement sur la carte, et permet au héros de les collecter pour monter en niveau. Bien sûr, chaque aimant ne peut être activé qu'une seule fois, vous devez donc les utiliser judicieusement !

L'objectif ultime du jeu est de collecter le plus de points d'expérience possible. Déterminez le plus grand montant de points d'expérience que vous pouvez avoir après secondes avec l'utilisation optimale des aimants.

Input

La seule ligne d'entrée contient quatre entiers t, c, k, m (1 \le t \le 10^9; 0 \le c \le 10^5; 1 \le k \le 10^5; 1 \le m \le 10^9) — la durée du jeu, les constantes définissant le gain d'expérience, et le nombre d'aimants.

Output

Affichez un seul entier — le montant maximum de points d'expérience que vous pouvez gagner à la fin du jeu.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Dans le premier cas de test, vous pouvez utiliser des aimants après la -ème et la -ème seconde — voir le tableau suivant :

Secondes écoulées

Aimant utilisé

non

non

oui

non

non

non

oui

Total exp. collecté

Niveau

Exp. non collectée

Exp. par seconde

Il peut être prouvé qu'il n'est pas possible de gagner plus d'expérience d'ici la fin du jeu.

Dans le deuxième cas de test, vous pouvez simplement utiliser un aimant après chaque seconde :

Secondes écoulées

Aimant utilisé

non

oui

oui

oui

oui

oui

oui

oui

oui

Total exp. collecté

Niveau

Exp. par seconde

Scoring

  1. ( points) : c = 0;

  2. ( points) : t \le 2 \cdot 10^3, m \le 3;

  3. ( points) : m,t \le 100;

  4. ( points) : t \le 2 \cdot 10^4;

  5. ( points) : pas de restrictions supplémentaires.