Pan Półsieć pracuje w firmie telekomunikacyjnej Bajkotel i jest projektantem protokołów sieciowych. Obecnie zajmuje się on protokołem umożliwiającym przesyłanie danych z jednego komputera do drugiego za pomocą kabla nowej generacji. Kablem takim można przesyłać sygnał o k różnych poziomach napięcia, przy czym napięcie to może się zmieniać co 1/n sekundy (1/n sekundy w trakcie której napięcie musi być stałe nazywamy impulsem). Dane przesyłane są w postaci paczek obejmujących m kolejnych impulsów (czyli przesłanie jednej paczki zajmuje m/n sekund).

Ze względów technicznych, w obrębie każdej paczki napięcie nie może być stałe, lecz co jakiś czas musi się zmieniać. Mówiąc ściślej, nie można przesyłać paczek danych zawierających l kolejnych impulsów o takim samym poziomie napięcia.

Jeżeli protokół umożliwia przesłanie x różnych paczek, to mówimy, że w jednej paczce możemy zakodować log₂x bitów informacji. Pan Półsieć zastanawia się, ile bitów informacji można przesłać maksymalnie w ciągu jednej sekundy.

Przykład

Załóżmy, że kablem można przesyłać sygnał o 2 różnych poziomach napięcia (k=2), które oznaczamy 0 i 1. Jeżeli napięcie może się zmieniać 20 razy na sekundę (n=20), paczki obejmują po 4 impulsy (m=4) i w obrębie każdej paczki żadne 3 kolejne impulsy nie mogą mieć takiego samego napięcia (l=3), to nie można przesyłać paczek: 0000, 0001, 1000, 1111, 1110, 0111. Można natomiast przesyłać paczki: 0010, 0011, 0100, 0110, 0101, 1101, 1100, 1011, 1001 i 1010. Ponieważ można przesyłać 10 różnych rodzajów paczek, więc w każdej paczce można zakodować log₂10 bitów informacji. W ciągu sekundy można przesłać 20/4 = 5 paczek, czyli 5*log₂10 ~ 16.6096 bitów informacji.

Zadanie

Napisz program, który:

• wczyta z pliku tekstowego pro.in liczby k, n, m i l opisujące protokół,
• obliczy maksymalną liczbę bitów informacji, jakie można przesłać w ciągu sekundy,
• zapisze w pliku tekstowym pro.out obliczoną liczbę bitów zaokrągloną w dół do najbliższej liczby całkowitej.

Wejście

W pierwszym wierszu pliku tekstowego pro.in zapisane są cztery liczby całkowite, pooddzielane pojedynczymi odstępami:

• liczba poziomów napięcia k (2 <= k <= 10),
• częstotliwość impulsów n (1 <= n <= 1000),
• rozmiar paczki danych m (1 <= m <= 100),
• liczbę l kolejnych impulsów w paczce, w obrębie których musi nastąpić zmiana napięcia (2 <= l <= m),

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu pliku tekstowego pro.out jedną liczbę całkowitą: maksymalną liczbę bitów, jakie można przesłać w ciągu sekundy, zaokrągloną w dół do najbliższej liczby całkowitej.

Przykład

Dla pliku wejściowego pro.in

2 20 4 3

poprawną odpowiedzią jest plik wyjściowy pro.out:

16