Background

Z works at a communications company. He is currently responsible for designing the company’s network protocol.

Problem Description

He is currently working on sending data from one computer to another through a cable.

In this cable there are $k$ different signal levels. Each second, the level changes $\frac{1}{n}$ times (we call $\frac{1}{n}$ seconds one pulse). A data packet contains $m$ consecutive pulses (that is, one packet is sent every $\frac{m}{n}$ seconds).

Due to technical reasons, the level in each packet cannot stay constant all the time; it must change multiple times. More precisely, any packet that contains a segment of $l$ consecutive pulses with the same level cannot be sent. Note that adjacent packets do not affect each other.

If there are $x$ different packets that can be sent, then a single packet contains $\log_2 x$ bits of information (which may be fractional). Z wants to know the maximum number of bits that can be sent in $1$ second.

Input Format

One line with four integers: the number of levels $k$, the pulse frequency $n$, the packet size $m$, and $l$, meaning that within one packet, there must not be $l$ consecutive pulses staying at the same level; within any such length, the level must change at least once.

Output Format

Output one integer: the maximum number of bits of information that can be sent in one second, rounded down.

2 20 4 3

16

Hint

For $100\%$ of the testdata, $2 \le k \le 10$, $1 \le n \le 1000$, $1 \le m \le 100$, $2 \le l \le m$, and $\frac{n}{m}$ is an integer not exceeding $10$.

Translated by ChatGPT 5