프로토콜

한 통신 회사가 새로운 케이블로 두 컴퓨터 사이에서 데이터를 전송하는 프로토콜을 설계하고 있다. 이 케이블은 $k$가지 서로 다른 전압 레벨의 신호를 보낼 수 있지만, 전압은 $1/n$초마다 한 번씩만 바뀔 수 있다. 전압이 일정하게 유지되는 이 $1/n$초 구간 하나를 임펄스(impulse)라고 부른다.

데이터는 연속한 $m$개의 임펄스로 이루어진 패킷 단위로 전송되므로, 패킷 하나를 보내는 데 $m/n$초가 걸린다.

기술적인 이유로 한 패킷 안에서 전압이 너무 오래 그대로 유지되면 안 된다. 즉, 한 패킷은 같은 전압 레벨의 임펄스가 연속으로 $l$개 나타나는 부분을 포함할 수 없다.

어떤 프로토콜로 서로 다른 패킷을 $x$가지 보낼 수 있다면, 패킷 하나에 $\log_2 x$ 비트의 정보를 담을 수 있다. 이때 1초 동안 최대 몇 비트의 정보를 보낼 수 있는지 구하는 것이 목표다.

예를 들어 케이블이 $2$가지 전압 레벨($k = 2$)을 제공하고 이를 $0$과 $1$로 나타내며, 전압이 1초에 $20$번 바뀌고($n = 20$), 각 패킷이 $4$개의 임펄스로 이루어지며($m = 4$), 같은 레벨이 연속으로 $3$개 나오면 안 된다($l = 3$)고 하자. 그러면 $0000$, $0001$, $1000$, $1111$, $1110$, $0111$ 패킷은 보낼 수 없고, $0010$, $0011$, $0100$, $0110$, $0101$, $1101$, $1100$, $1011$, $1001$, $1010$ 패킷은 보낼 수 있다. 서로 다른 패킷이 $10$가지이므로 패킷 하나에 $\log_2 10$ 비트를 담을 수 있다. 1초 동안 $20/4 = 5$개의 패킷을 보내므로 $5 \cdot \log_2 10 \approx 16.6096$ 비트의 정보를 보낼 수 있다.

프로토콜을 나타내는 정수 $k$, $n$, $m$, $l$을 읽어 1초 동안 보낼 수 있는 정보의 최대 비트 수를 구하고, 그 값을 소수점 아래로 버림한 정수를 출력하는 프로그램을 작성하라.

첫째 줄에 네 개의 정수가 공백 하나로 구분되어 주어진다.

• 전압 레벨의 수 $k$ ($2 \le k \le 10$),
• 임펄스의 주파수 $n$ ($1 \le n \le 1000$),
• 패킷의 크기 $m$ ($1 \le m \le 100$),
• 금지되는 연속 길이 $l$ ($2 \le l \le m$): 한 패킷은 같은 전압 레벨의 임펄스가 연속으로 $l$개 나오는 부분을 포함할 수 없다.

$n/m$은 $10$ 이하의 정수임이 보장된다.

1초 동안 보낼 수 있는 정보의 최대 비트 수를 소수점 아래로 버림한 정수 하나를 첫째 줄에 출력한다.