KiloBoom#519

KiloBoom

2 sekundy
512 megabajtów
Bardzo trudne

Grasz w swoją ulubioną grę komputerową — KiloBoom.

W tej grze wcielasz się w bohatera walczącego z falami potworów. Z potworów po ich pokonaniu wypadają punkty doświadczenia, a zbierając te punkty, możesz zwiększyć poziom swojego bohatera. W dowolnym momencie gry poziom bohatera oblicza się w następujący sposób: niech będzie całkowitą liczbą punktów doświadczenia zebranych do tej pory. Wtedy dla s=0 jest l=0, a w przeciwnym razie l = \lfloor \log_2 (s) \rfloor ^\dagger. Innymi słowy, musisz podwoić swoje punkty, aby awansować na kolejny poziom.

^\dagger \lfloor \log_2 (x) \rfloor równa się największej liczbie całkowitej , dla której 2^k \le x. Na przykład, \lfloor \log_2 (23) \rfloor = 4, \lfloor \log_2 (8) \rfloor = 3.

Gra trwa sekund, a po każdej sekundzie potwory, z którymi walczysz, dają l \cdot c + k punktów doświadczenia. W ten sposób podstawowy przyrost doświadczenia wynosi punktów na sekundę, a z każdym awansem na poziom wzrasta o .

Jednak jest problem — twoja klawiatura właśnie się zepsuła i nie możesz poruszać swoim bohaterem, a więc nie możesz zbierać punktów doświadczenia wypadających z wrogów. Na szczęście masz magnesów — każdy magnes, po aktywacji, wciąga wszystkie punkty doświadczenia znajdujące się obecnie na mapie i pozwala bohaterowi je zebrać, aby awansować. Oczywiście każdy magnes można aktywować maksymalnie raz, więc musisz ich używać mądrze!

Ostatecznym celem gry jest zebranie jak największej liczby punktów doświadczenia. Określ największą liczbę punktów doświadczenia, jaką możesz zdobyć po sekundach przy optymalnym wykorzystaniu magnesów.

Dane wejściowe

Jedyna linia wejściowa zawiera cztery liczby całkowite 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) — czas trwania gry, stałe definiujące przyrost doświadczenia oraz liczbę magnesów.

Dane wyjściowe

Wypisz jedną liczbę całkowitą — maksymalną liczbę punktów doświadczenia, jaką możesz zdobyć do końca gry.

Przykłady

Przykład 1

Loading
Loading

Przykład 2

Loading
Loading

Uwaga

W pierwszym teście możesz użyć magnesów po -iej i -tej sekundzie — zobacz poniższą tabelę:

Minuty

Magnes użyty

nie

nie

tak

nie

nie

nie

tak

Całkowite zebrane exp.

Poziom

Exp. nie zebrane

Exp. na sekundę

Można wykazać, że nie jest możliwe zdobycie większej liczby punktów doświadczenia do końca gry.

W drugim teście możesz po prostu użyć jednego magnesu po każdej sekundzie:

Minuty

Magnes użyty

nie

tak

tak

tak

tak

tak

tak

tak

tak

Całkowite zebrane exp.

Poziom

Exp. na sekundę

Punktacja

  1. ( punktów): c = 0;

  2. ( punktów): t \le 2 \cdot 10^3, m \le 3;

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

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

  5. ( punkty): brak dodatkowych ograniczeń.