#C2023J. 逛第二次超市

逛第二次超市

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

没想到吧,我居然在这里!

题目描述

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

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

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

输入格式

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

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

输出格式

输出一个小数xx,为野豌豆最坏情况下抽到奖品的期望价值,要求与答案的相对误差或绝对误差不超过10610^{-6}

也就是说,如果你给出的答案是aa,正确答案是bb,你的答案被认为是正确的当且仅当abmax(1,b)<106\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%30\%的数据,1n1001\le n \le 1001ai1001\le a_i\le 100nS1000n\le S\le 1000

对于100%100\%的数据,1n3×1051\le n \le 3\times10^51ai1061\le a_i\le 10^61wi1091\le w_i\le 10^9nS109n\le S\le 10^9

提示

对于第一组数据,可以证明当所剩奖品的价值分别是1,1,1,5,6,7,101,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,13000,1000,64800,2,1,答案为13760.613760.6