题目描述

魏总，也就是 DP 魏又开始刷 DP 了。一共有 $n$ 道题，第 $i$ 道题魏总原本需要 $u_i$ 秒的时间。不过，为了表达对这些水题的藐视，魏总决定先睡 $k$ 秒再开始刷题。魏总并不清楚自己会睡多久，只知道 $k$ 是不超过 $m$ 的正实数。并且魏总还忘了这节课有多长，只记得这节课的长度 $T$（单位：秒）是在 $L$ 到 $R$ 之间。（魏总是从开始上课的时候开始睡的）睡醒后，魏总神奇地发现自己做每道题所需的时间变成了原来的 $k$ 倍。不过 DP 魏就是 DP 魏，他可以同时做这 $n$ 道 DP，互不影响。

魏总本想虐场，但他很快发现自己低估这些题了。于是他决定将题分为 HARD 和 EASY。对于每道 HARD 的题，他希望能最晚在下课后 $late_i$ 秒内完成，而对于 EASY 的题，他希望在下课前 $rest_i$ 秒之前完成。

求魏总达到目标的概率。

输入格式

第一行，一个整数 $n$。

第二行，三个实数 $m,L,R$。

第三行，$n$ 个整数，第 $i$ 个为 $u_i$。

接下来 $n$ 行，每行一个字符串和一个整数，字符串为 HARD 或 EASY，整数为对应的 $late_i$ 或 $rest_i$。

输出格式

一行，魏总达到目标的概率，保留 $4$ 位小数。

2
1.50 0.630 1.810
2 2 
EASY 1
EASY 0

0.0618

数据规模与约定

对于 $100\%$ 的数据，$0<n \le 10^5$，$0<m<10^5$，$0<L<R<10^5$，$0<late_i,rest_i \le 10^5$。