You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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

没想到吧，我居然在这里！

题目描述

野豌豆正在参加超市抽奖活动，抽奖活动共有$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(n\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

4.4285714286

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

13760.6000000000

数据范围

对于$30\%$的数据，$1\le n \le 100$，$1\le a_i\le 100$，$n\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$ ，$n\le S\le 10^9$。

提示

对于第一组数据，可以证明当所剩奖品的价值分别是$1,1,1,5,6,7,10$时，野豌豆可以抽到的期望价值最小，为$\frac 37\times 1 + \frac {1}{7}\times 5 + \frac 17 \times 6+\frac 17\times 7 + \frac 17\times 10 = \frac {31}{7} $

对于第二组数据，因为每种奖品都至少剩下一份，所以所剩商品的价值只能为$3000,1000,64800,2,1$，答案为$13760.6$。