The Bold And Diverse Investors LLC is working on a new project. They have recently acquired several auction vouchers that can be used to purchase shares of some new companies. You have been left in charge of determining which lots to bid on. When you bid on a lot you will get a percentage of the lot based on the number of vouchers you bid on the lot and the total number of vouchers bid by others on the lot. For example, let's assume you bid $$$22$$$ vouchers on a lot and the total vouchers bid by others on the lot is $$$66$$$, then your percentage of the lot will be $$$22 / (22 + 66) = 25\%$$$. If this lot has a profit of $$${\$}500$$$, then your profit from this lot will be $$${\$}500 \cdot 25\% = {\$}125$$$.
You have paid quite handsomely for information regarding how many vouchers (not including yours) are going to be placed on each lot, and the expected profit of each lot. Your job will be to place your bids such that you maximize your expected profit.
Given the number of vouchers you possess, the value of each lot, and the number of bids placed by others on each lot, determine the maximum expected profit you can get by bidding optimally.
The first input line contains two integers: $$$n$$$ $$$(1 \le n \le 10^5)$$$ representing the number of lots to bid on, and $$$v$$$ $$$(1 \le v \le 10^9)$$$ representing the number of vouchers you possess. Each of the following $$$n$$$ input lines contains two integers, representing (respectively) the expected profit and the number of vouchers placed by others for a lot. The $$$i$$$-th input line contains $$$p_i$$$ and $$$v_i$$$ $$$(1 \le p_i \le 10^9; 1 \le v_i \le 10^9)$$$, providing the info for the $$$i$$$-th lot.
Print on a single line by itself a single number: the maximum possible expected profit. Answers within $$$10^{-6}$$$ absolute or relative of the expected answers will be considered correct.
1 22 500 66
125.0
2 3 1 1 1 1
1.1666666666666667
| 2022 UCF Local Programming Contest |
|---|
| Finished |
