Protocols

A telecommunications company is designing a protocol to send data between two computers over a new cable. The cable can carry signals at $k$ different voltage levels, but the voltage may change only every $1/n$ of a second. Such a $1/n$-second interval, during which the voltage stays constant, is called an impulse.

Data are sent in packets of $m$ consecutive impulses, so transmitting one packet takes $m/n$ seconds.

For technical reasons the voltage may not stay constant for too long inside a packet: a packet may not contain $l$ consecutive impulses at the same voltage level.

If a protocol can send $x$ different packets, then each packet carries $\log_2 x$ bits of information. The task is to find how many bits of information can be sent in one second.

For example, suppose the cable offers $2$ voltage levels ($k = 2$), written $0$ and $1$. Let the voltage change $20$ times per second ($n = 20$), let each packet contain $4$ impulses ($m = 4$), and let no $3$ consecutive impulses share the same level ($l = 3$). Then the packets $0000$, $0001$, $1000$, $1111$, $1110$ and $0111$ cannot be sent, while $0010$, $0011$, $0100$, $0110$, $0101$, $1101$, $1100$, $1011$, $1001$ and $1010$ can. Since $10$ different packets are available, each packet carries $\log_2 10$ bits. In one second $20/4 = 5$ packets are sent, giving $5 \cdot \log_2 10 \approx 16.6096$ bits of information.

Write a program that reads the integers $k$, $n$, $m$ and $l$ describing the protocol, computes the maximum number of bits of information that can be sent in one second, and prints that number rounded down to the nearest integer.

The first line contains four integers separated by single spaces:

• the number of voltage levels $k$ ($2 \le k \le 10$),
• the impulse frequency $n$ ($1 \le n \le 1000$),
• the packet size $m$ ($1 \le m \le 100$),
• the forbidden run length $l$ ($2 \le l \le m$): a packet may not contain $l$ consecutive impulses at the same voltage level.

It is guaranteed that $n/m$ is an integer not greater than $10$.

Print a single integer: the maximum number of bits of information that can be sent in one second, rounded down to the nearest integer.