背景

qq820186690很喜欢玩游戏，无论在家里，在寝室，在机房，在厕所。
achen有很多罪恶の手，呃......塑料手，具体我们题目描述中说。

描述

qq820186690和achen住在同一个寝室，他们是很好的朋友和室友，算上他们俩寝室一共住了K个同学。
有一天，qq820186690突然意识到了玩游戏的危害，因此他于2012-9-3在发了一篇微博：

这很奇怪啊，qq820186690如果被发现玩游戏或者干一些与学习无关的事就会将一些“手”切成碎片。这个逻辑真是厉害了，不是吗？
我们将这些与qq820186690学习无关的事称作“坏事”。现在我们知道qq820186690如果在寝室待上T分钟就会开始做“坏事”，他会停止做这些“坏事”当他被achen警告或者他离开寝室。请注意，如果qq820186690被achen警告后又在宿舍待上T分钟，他又会重新干“坏事”。
achen注意到了qq820186690发布的这篇奇怪的微博，但是他是一个非常给力的室友，所以他决定冒着失去自己“手”的危险去警告qq820186690。辛运的是，achen有M只塑料玩具手，所以当qq820186690被警告时，他只会将这些玩具手切成碎片。
那么问题来了。作为生活老师的你只知道初始时没有人在寝室，并且我们听到了N声门开关的声音。我们准确地记录了这N次门开关的声音的发出时间，但是我们并不知道谁造成了这些声音，这意味着有N人/次进入或离开了寝室，任何K个住在寝室的同学有相同的概率进入/离开。
我们想要知道24小时(1440分钟)后可怜的achen期望剩下的塑料手的个数。
请注意achen使用塑料手去阻止qq820186690做“坏事”并不花费时间。这意味着一旦achen进入寝室，一只塑料手将会立即用于阻止qq820186690做“坏事”。但是如果没有塑料手剩余，achen便无法阻止qq820186690做“坏事”了。

格式

输入格式

第一行包含4个整数T(1≤T≤100),N(1≤N≤100),M(1≤M≤100)和K(2≤K≤8)，它们的意义已经被描述。
第二行包含N个整数ti(0≤ti≤1440,0≤i<N)，表示在时刻ti有一个学生进入或离开了寝室。
数据保证这N个时刻由严格递增顺序给出。

输出格式

输出在时刻1440，achen期望拥有的塑料手个数，保留到6位小数。

样例1

样例输入1

60 2 10 2 
200 260 

样例输出1

5.000000 

样例2

样例输入2

100 2 8 5 
1340 1341

样例输出2

7.960000

限制

每个测试点1s

提示

数据范围：
对于30%的数据，满足N≤10且M≤10。
对于60%的数据，满足N≤50且M≤30。
对于100%的数据，满足N≤100且M≤100,1≤T≤100,2≤K≤8,0≤ti≤1440。
数据保证随机且无误。

后记

achen：“什么？！我的罪恶の手才100只？？？出题人你在逗我，数据范围应该是M<=10^6！”

Source

Bill_Yang改编自ZOJ