Ви граєте у свою улюблену комп'ютерну гру — KiloBoom.
У цій грі ви граєте за героя, який бореться з хвилями монстрів. Монстри скидають очки досвіду після того, як ви їх переможете, і, збираючи ці очки, ви можете підвищити рівень свого героя. На будь-якому етапі гри рівень героя розраховується наступним чином: нехай буде загальною кількістю очок досвіду, зібраних до цього моменту, тоді l=0, якщо s=0, і l = \lfloor \log_2 (s) \rfloor ^\dagger в іншому випадку. Іншими словами, вам потрібно подвоїти свої очки, щоб "підвищити рівень".
^\dagger \lfloor \log_2 (x) \rfloor дорівнює найбільшому цілому числу , такому що 2^k \le x. Наприклад, \lfloor \log_2 (23) \rfloor = 4, \lfloor \log_2 (8) \rfloor = 3.
Гра триває секунд, і після кожної секунди монстри, з якими ви боретеся, скидають l \cdot c + k очок досвіду. Таким чином, базове отримання досвіду становить очок за секунду, а з кожним підвищенням рівня воно збільшується на .
Однак є проблема — ваша клавіатура тільки що зламалася, і ви не можете рухати свого героя, а отже, не можете підбирати очки досвіду, скинуті ворогами. На щастя, у вас є магнітів — кожен магніт, як тільки його активують, всмоктує всі очки досвіду, які зараз на карті, і дозволяє героєві зібрати їх для підвищення рівня. Звичайно, кожен магніт можна активувати не більше одного разу, тому ви повинні використовувати їх розумно!
Головна мета гри полягає в тому, щоб зібрати якомога більше очок досвіду. Визначте найбільшу кількість очок досвіду, яку ви можете мати після секунд з оптимальним використанням магнітів.
Єдиний рядок вхідних даних містить чотири цілі числа 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) — тривалість гри, константи, що визначають отримання досвіду, та кількість магнітів.
Виведіть єдине ціле число — максимальна кількість очок досвіду, яку ви можете отримати до кінця гри.
Приклад 1
Приклад 2
У першому тестовому випадку ви можете використовувати магніти після -ї та -ї секунд — дивіться наступну таблицю:
Пройшло секунд | |||||||
Використано магніт | ні | ні | так | ні | ні | ні | так |
Загальна кількість досвіду | |||||||
Рівень | |||||||
Досвід не зібрано | |||||||
Досвід за секунду |
Можна показати, що неможливо отримати більше досвіду до кінця гри.
У другому тестовому випадку ви можете просто використовувати один магніт після кожної секунди:
Пройшло секунд | |||||||||
Використано магніт | ні | так | так | так | так | так | так | так | так |
Загальна кількість досвіду | |||||||||
Рівень | |||||||||
Досвід за секунду |
( балів): c = 0;
( балів): t \le 2 \cdot 10^3, m \le 3;
( бали): m,t \le 100;
( бали): t \le 2 \cdot 10^4;
( бали): без додаткових обмежень.