[POI2002]协议

题目背景

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

目前他致力于通过一条电缆从一台电脑向另一台电脑发送数据。

在这条电缆中有 $k$ 种不同的电平，每秒电平会变化 $\frac{1}{n}$ 次 (我们称 $\frac{1}{n}$ 秒为一个脉冲)。一个数据包包含 $m$ 个连续的脉冲。(即每 $\frac{m}{n}$ 秒发送一个数据包)。

由于技术原因, 每个包里的电平不能一直稳定为一个常数, 而是需要多次改变。严格地讲, 包含连续 $l$ 个电平相同的脉冲的数据包将不能被发送。注意相邻两个数据包互不影响。

如果可能被发送的数据包共有 $x$ 种，那么单个数据包会包含 $log_2x$ 位信息(可以为一个小数)。Z 想知道在 $1$ 秒内最多能发送多少位信息。

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

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

2 20 4 3

对于 $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$ 的整数。