题目背景

Alex 正在收拾行李，现在轮到打包袜子。

Alex 的袜子只有两种尺寸：小号和大号。小号袜子的尺寸记为 sizeSmall，大号袜子的尺寸记为 sizeBig。

抽屉里一共有 $N$ 只袜子。每只袜子都有一种颜色 color[i]，以及一个尺寸 size[i]。

Alex 决定旅途中只需要从这 $N$ 只袜子中带走 $K$ 只。于是他每次从抽屉中随机选择一只袜子，放进行李中，重复 $K$ 次。

如果当前抽屉中还剩 $p$ 只袜子，它们的实际尺寸分别为

其中每个 $s_i$ 都等于 sizeSmall 或 sizeBig，那么第 $i$ 只袜子被选中的概率为

Alex 希望自己的袜子搭配得好看，所以他想知道：最终选出的 $K$ 只袜子中，至少有两只袜子颜色相同的概率是多少。注意，这两只袜子的尺寸可以不同。

输入格式

第一行包含两个整数 $N,K$，分别表示抽屉中袜子的总数，以及 Alex 要选择的袜子数量。

第二行包含两个整数 sizeSmall 和 sizeBig，分别表示小号袜子和大号袜子的实际尺寸。

接下来 $N$ 行，第 $i$ 行包含两个整数 color[i] 和 size[i]：

• color[i] 表示第 $i$ 只袜子的颜色，是一个 $1$ 到 $N$ 之间的整数；
• size[i]=0 表示这是一只小号袜子，实际尺寸为 sizeSmall；
• size[i]=1 表示这是一只大号袜子，实际尺寸为 sizeBig。

输出格式

输出一个实数，表示 Alex 选出的 $K$ 只袜子中，至少存在两只颜色相同袜子的概率。

数据范围与限制

• $1 \le N < 200$；

• $1 \le K \le N$；

• $1 \le \text{sizeSmall},\text{sizeBig} \le 2000$；

• 对于每个测试点，如果你的答案与标准答案的绝对误差不超过 $10^{-5}$，可获得该测试点满分；

• 建议使用 long double 存储实数；

• 官方评测环境中，long double 占 $12$ 字节；

• 使用 scanf / printf 读写 long double 时，应使用 %Lf。

样例

输入

4 2
1 2
1 1
2 0
1 1
2 1

输出

0.3333333333333