#3923. [Poi2002]协议

[Poi2002]协议

[POI2002]协议

题目背景

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

题目描述

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

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

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

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

输入格式

输入一行四个整数:电平种类 kk, 脉冲频率 nn, 单个数据包大小 mm, 在一个数据包中不能连续保持相同电平的脉冲的数目 ll, 在这个范围内电平至少要改变一次。

输出格式

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

样例 #1

样例输入 #1

2 20 4 3

样例输出 #1

16

提示

对于 100%100\% 的数据,2k102 \le k \le 101n10001 \le n \le 10001m100 1 \le m \le 1002lm2 \le l \le mnm\frac{n}{m} 是一个不超过 1010 的整数。