本题与逛第二次超市的区别仅在于盲盒中剩下物品的要求，以及本题$S$的数据范围为$1\le S\le 10^9$。

本题并不难。如果你不会概率与期望，可以回过头看看2022年新生赛的B题。

题目描述

野豌豆正在参加超市抽奖活动，抽奖活动共有$n$个奖项，奖池中第$i$个奖项总共有$a_i$份，如果抽中第$i$个奖项将会获得一份价值为$w_i$的奖品。抽奖方式为从盲盒里抽签，初始时盲盒中总共有$m=\sum_{i=1}^na_i$份签，其中表示第$i$个奖项的签数总共有$a_i$个。商店老板绝对公平，保证你抽到每个签的概率是相等的。

现在野豌豆仅获得了一次抽奖的机会，不过当野豌豆逛完超市来抽奖时已经来晚了，商店老板告诉你现在盲盒里剩下不超过$S$份签了（即剩下奖品的总数不超过$S$个），但好消息是盲盒中至少剩下了一份奖品。野豌豆此时心中有种不祥的预感，于是他想问你在最坏情况下，自己抽到奖品的期望价值最小是多少。

关于期望的定义：假设抽到第$i$个奖项的概率为$p_i$，那么抽奖一次获得奖品的期望价值为$E=\sum_{i=1}^n p_iw_i$

输入格式

第一行包含两个正整数$n$和$S$，表示总共有$n(1\le n\le 300000)$个奖项，且余下奖品总数不超过$S(1\le S\le 10^9)$个。

第$i+1$行包含两个正整数$a_i, w_i$，表示第$i$个奖项在初始时总共有$a_i(1\le a_i\le 10^6)$份，抽中第$i$个奖项时会获得价值为$w_i(1\le w_i\le 10^9)$的奖品。

输出格式

输出一个小数$x$，为野豌豆最坏情况下抽到奖品的期望价值，你的答案与正确答案的相对误差或绝对误差不超过$10^{-6}$。

也就是说，如果你给出的答案是$a$，正确答案是$b$，你的答案被认为是正确的当且仅当$\frac {|a-b|}{\max{(1,b)}}<10^{-6}$。

样例

5 10
3 1
4 5
3 6
1 7
1 10

1.0000000000

5 5
20 3000
10 1000
3 64800
100 2
100 1

1.0000000000

数据范围

对于$30\%$的数据，$1\le n \le 100$，$1\le a_i\le 100$，$1\le S\le 1000$。

对于$100\%$的数据，$1\le n \le 3\times10^5$，$1\le a_i\le 10^6$，$1\le w_i\le 10^9$ ，$1\le S\le 10^9$。