#2978. [Poi2002]协议

内存限制:128 MiB 时间限制:1 Sec

题目描述

Mr ZHU 在一个通讯公司工作,他承担了公司的网络协议设计任务。目前他致力于通过一条电缆从一台电脑发送数据到另一台电脑。在电缆中有k 种不同的电平,而每秒电平有1/n 种变化 (1/n 秒这个常数,我们称之为一个脉冲).数据打包发送时,包含了m个连续的脉冲。(即每 m/n 秒发送一个包).
由于技术原因, 在每个包里的电平并稳定为一个常数, 而是不得不一次次改变. 严格地讲,包含连续l个脉冲电平相同的数据包将不能发送.
如果某种协议允许发送x 个不同的包,那么能对一个包进行log2x二进制位的编码. Mr ZHU 想知道在1秒内最多能发送多少位信息.
例如
假设电缆允许我门发送2种不同的电平的信息(k=2), 我们用0 和 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 and 1010. 当一个要发送10个不同种类的包,我们对每个包进行log210 位信息编码. 在一秒内可以发送20/4 = 5 个包, 也就是5*log210 ~ 16.6096 位信息.

输入格式

 有四个整数:
  • 电平种类 k (2 <= k <= 10),
  • 脉冲的频率 n (1 <= n <= 1000),
  • 数据包的大小 m (1 <= m <= 100),
  • 在一个包中连续脉冲的数目l, 也就是说在这个范围内必须改变电平 (2 <= l <= m),
我们假设 n/m 是一个不超过10的整数.

输出格式

写入一个整数,为一秒内最大能发送数据包的位数,答案四舍五入取整

样例

样例输入


			
2 20 4 3





样例输出


			
16

数据范围与提示