#P17979. Market

Market

Market

题目描述

你准备在接下来的 nn 天内反复买卖同一套公寓。开始时没有公寓,并拥有 1010010^{100} 的资金。你在任何时刻至多拥有一套公寓。

第 ii 天的公寓价格 cic_i 是在实数区间 [ai,bi][a_i,b_i] 上均匀随机选取的数,其中 ai<bia_i<b_i。不同天的价格独立选取。

通常,你在第 ii 天开始时才知道当天的实际价格 cic_i,随后决定是否交易:若没有公寓,可以以 cic_i 买入;若拥有公寓,可以以 cic_i 卖出;也可以不交易。

在第一天开始之前,你有一次提前获知信息的机会:先选定恰好 kk 个日期,然后立即得知这些日期的实际价格。对于未选择的日期,仍然只能在当天开始时得知价格。选择日期集合时,你还不知道任何一天的实际价格。

第 nn 天结束时,你必须没有公寓。利润定义为最终资金减去初始资金。

如果你最优地选择提前获知价格的日期,并根据已知信息最优地安排每天的交易,求利润的最大期望值。

输入格式

第一行两个整数 n,kn,k。

接下来 nn 行,每行两个整数 ai,bia_i,b_i,描述第 ii 天价格的均匀分布区间。

输出格式

输出一个实数,表示最大期望利润。

允许的相对或绝对误差为 10−610^{-6}。具体地,若正确答案为 yy,输出为 xx,则要求

∣x−y∣≤10−6max⁡(1,y).|x-y|\le10^{-6}\max(1,y).

小数点后最多可以输出 2020 位数字。

数据范围

1≤n≤3000001\le n\le300000,0≤k≤n0\le k\le n,1≤ai<bi≤1061\le a_i<b_i\le10^6。

样例 1

输入

4 0
10 30
10 30
40 50
30 60

输出

28.75

样例 2

输入

4 1
10 30
10 30
40 50
30 60

输出

31.3888888889

样例 3

输入

6 3
10 50
30 70
50 70
30 50
30 40
10 40

输出

33.6805555556

样例说明

第一组不能提前获知任何一天的价格。一种最优策略是在第 11 或第 22 天买入,期望支出为 17.517.5,并在第 33 或第 44 天卖出,期望收入为 46.2546.25。

第二组最优选择是提前知道第 44 天的价格,答案为 3171831\dfrac7{18}。第三组可以最优地选择日期集合 {2,3,6}\{2,3,6\}。