KiloBoom#519

KiloBoom

2 секунди
512 мегабайтів
Дуже складна

Ви граєте у свою улюблену комп'ютерну гру — 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

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У першому тестовому випадку ви можете використовувати магніти після -ї та -ї секунд — дивіться наступну таблицю:

Пройшло секунд

Використано магніт

ні

ні

так

ні

ні

ні

так

Загальна кількість досвіду

Рівень

Досвід не зібрано

Досвід за секунду

Можна показати, що неможливо отримати більше досвіду до кінця гри.

У другому тестовому випадку ви можете просто використовувати один магніт після кожної секунди:

Пройшло секунд

Використано магніт

ні

так

так

так

так

так

так

так

так

Загальна кількість досвіду

Рівень

Досвід за секунду

Оцінювання

  1. ( балів): c = 0;

  2. ( балів): t \le 2 \cdot 10^3, m \le 3;

  3. ( бали): m,t \le 100;

  4. ( бали): t \le 2 \cdot 10^4;

  5. ( бали): без додаткових обмежень.