问题 5047 --偷学计划

5047: 偷学计划

题目描述

  小 K 是一个酷爱偷学的巨佬,喜欢利用一切碎片时间偷学。很快,他就写完了所有作业。为了成为班上最会偷学的学生,他想向老师继续要作业。已知有 $N$ 份作业,一开始小K都没有做过。当他向老师要作业是,老师会有 $P_i$ 的概率给他第 $i$ 种作业。第一次做完第 $i$ 份作业,他的愉悦度就会增加就会 $W_i$。小 K 在 $0.025\operatorname{ms}$ 内算出了他能够获得的愉悦度以及要作业的期望次数,但是他想为难你一下,让你在 $1 \operatorname{s}$ 内解决这个问题。

输入

第一行一个整数 $N$,表示有 $N$ 份作业。
接下来 $N$ 行,每行一个实数 $P_i$ 和正整数 $W_i$,表示第 $i$ 份作业被拿出来的概率和第一次完成可以获得的愉悦度。

输出

第一行一个整数表示可以获得的最大喜悦值。
第二行一个实数表示获得这个喜悦值的期望购买次数,保留 $3$ 位小数。

样例输入输出

输入#1 复制
3
0.1 2
0.2 5
0.3 7
输出#1 复制
14
12.167

提示

对于 $10\%$ 的数据,$N=1$;
对于 $30\%$ 的数据,$N \leq 5$;
对于 $100\%$ 的数据,$1 \leq N \leq 20$,$0 < W_i \leq 10^9$,$0 < P_i \leq 1$,$0 < \sum P_i \leq 1$。

序号 标题 作者 发表时间 费用 订购数 操作