#16117. 现代仓库的物资整理

现代仓库的物资整理

以下是根据参考信息整理的题目内容:

第一题:现代仓库的物资整理

题目描述

在某大型物流中心,仓库管理员小陈接到了一项紧急任务。他需要在接下来的 MM 小时内,对仓库里 NN 类不同的物资进行整理和分拣,以便快速完成后续的发货工作。

仓库中现存 NN 类物资,每类物资由于数量、体积和存放位置不同,完成整理所需要的时间也各不相同;同时,每类物资及时完成整理后,对后续发货效率提升的价值也有所差异。并且,每类物资可以进行部分整理,即可以只投入部分时间去整理该类物资,获得相应比例的发货效率提升价值。对于第 ii 类物资(1iN1 \le i \le N),完成全部整理需要花费 tit_i 小时,其全部整理完成后对发货效率提升的价值为 viv_i

小陈希望在有限的 MM 小时内,合理安排物资整理的顺序,使得整理完成的物资对发货效率提升的总价值达到最大,从而顺利完成这次紧急任务。

请你帮助小陈计算,他最多能够实现的发货效率提升总价值是多少?

输入格式

第一行包含两个整数 NNMM,分别表示物资的种类数和小陈拥有的总时间。 接下来 NN 行,每行两个整数 tit_iviv_i,表示整理第 ii 类物资所需时间和其对发货效率提升的价值。

输出格式

输出一个浮点数,表示小陈最多能够实现的发货效率提升总价值,结果保留 2 位小数。

输入输出样例 #1

输入 #1

4 5
1 2
2 4
3 4
2 2

输出 #1

8.67

说明/提示

对于 30% 的数据,1N101 \le N \le 101M201 \le M \le 20。 对于 100% 的数据,1N1001 \le N \le 1001tiM10001 \le t_i \le M \le 10001vi10001 \le v_i \le 1000