P5945 [POI 2002] 协议

Z 在一个通讯公司工作。 目前他承担了公司的网络协议设计任务。

目前他致力于通过一条电缆从一台电脑向另一台电脑发送数据。 在这条电缆中有 $k$ 种不同的电平， 每秒电平会变化 $\frac{1}{n}$ 次 (我们称 $\frac{1}{n}$ 秒为一个脉冲)。 一个数据包包含 $m$ 个连续的脉冲。(即每 $\frac{m}{n}$ 秒发送一个数据包)。 由于技术原因, 每个包里的电平不能一直稳定为一个常数, 而是需要多次改变。 严格地讲, 包含连续 $l$ 个电平相同的脉冲的数据包将不能被发送。 注意相邻两个数据包互不影响。 如果可能被发送的数据包共有 $x$ 种， 那么单个数据包会包含 $\log_2x$ 位信息(可以为一个小数)。Z 想知道在 $1$ 秒内最多能发送多少位信息。

输入一行四个整数：电平种类 $k$， 脉冲频率 $n$， 单个数据包大小 $m$， 在一个数据包中不能连续保持相同电平的脉冲的数目 $l$， 在这个范围内电平至少要改变一次。

输出一个整数，为一秒内最大能发送信息的位数，答案向下取整。

对于 $100\%$ 的数据，$2 \le k \le 10$，$1 \le n \le 1000$，$ 1 \le m \le 100$，$2 \le l \le m$，$\frac{n}{m}$ 是一个不超过 $10$ 的整数。