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.
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.
Wypisz jedną liczbę całkowitą — maksymalną liczbę punktów doświadczenia, jaką możesz zdobyć do końca gry.
Przykład 1
Przykład 2
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ę |
( punktów): c = 0;
( punktów): t \le 2 \cdot 10^3, m \le 3;
( punkty): m,t \le 100;
( punkty): t \le 2 \cdot 10^4;
( punkty): brak dodatkowych ograniczeń.