You are playing your favourite computer game — KiloBoom.
In this game, you're playing as a hero fighting waves of monsters. Monsters drop experience points after you defeat them, and by collecting these points, you can increase your hero's level. At any point in the game, the hero's level is calculated as follows: let be the total amount of experience points collected so far, then l=0 if s=0, and l = \lfloor \log_2 (s) \rfloor ^\dagger otherwise. In other words, you need to double your points to "Level Up".
^\dagger \lfloor \log_2 (x) \rfloor equals the largest integer such that 2^k \le x. For example, \lfloor \log_2 (23) \rfloor = 4, \lfloor \log_2 (8) \rfloor = 3.
The game goes for seconds, and after each second, monsters that you fight drop l \cdot c + k experience points. This way, base experience gain is points per second, and with each Level-Up, it increases by .
However, there is a problem — your keyboard just broke, and you can not move your hero, and hence can not pick up the experience points dropped by enemies. Luckily, you have magnets — each magnet, once activated, sucks in all of the experience points currently on the map, and lets the hero collect them to Level-Up. Of course, each magnet can be activated at most once, so you must use them wisely!
The ultimate goal of the game is to collect as many experience points as possible. Determine the largest amount of experience points you can have after seconds with the optimal usage of the magnets.
The only line of input contains four integers 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) — the duration of the game, constants defining experience gain, and the number of magnets.
Output a single integer — maximum amount of experience points you can gain by the end of the game.
Example 1
Example 2
In the first test case, you can use magnets after the -nd and -th seconds — see the following table:
Seconds passed | |||||||
Magnet used | no | no | yes | no | no | no | yes |
Total exp. collected | |||||||
Level | |||||||
Exp. not collected | |||||||
Exp. per second |
It can be shown that it's not possible to gain more experience by the end of the game.
In the second test case, you can just use one magnet after each second:
Seconds passed | |||||||||
Magnet used | no | yes | yes | yes | yes | yes | yes | yes | yes |
Total exp. collected | |||||||||
Level | |||||||||
Exp. per second |
( points): c = 0;
( points): t \le 2 \cdot 10^3, m \le 3;
( points): m,t \le 100;
( points): t \le 2 \cdot 10^4;
( points): no additional restrictions.