配点: 700 点
問題文
除了部长 E869120 外,研究会还有 1 到 N 最多 N 人的成员。
研究会的成员都参加了 AtCoder 的比赛,E869120 目前的评分是 A、部員 i 的当前评分是 a_i 。
。
他为了让研究会变得更强,对除了自己的其他成员进行了如下操作若干次。
-
操作 1: 部員 1 选择一个人进行教育。
部員 i 该值应乘以 1 每进行一次教育,该成员的评分将 b_i 上涨。
,另外,如果多次教育同一成员,每次评分都会 b_i 上涨。
。 此时,E869120 每次会消耗体力 c_i 。 -
操作 2:从当前成员中选择 1 人施加压力让其退会。
部員 i 当退会时,E869120 消耗体力 d_i 。
。 E869120 想在消耗的体力总和不超过 K 的情况下,通过这些操作,使包括他本人在内的研究会成员 AtCoder 评分的平均值达到最大化。
此时,请求出可以达到的最大平均评分。
此外,E869120 不能自我教育,也不能退出社团。
制約
- 所有输入均为整数。
- 1 \leq N \leq 1 \ 500
- 1 \leq K \leq 1 \ 500
- 1 \leq A \leq 10^9
- 1 \leq a_i, b_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq c_i, d_i \leq K (1 \leq i \leq N)
小課題
这项作业需要 2 有两个子作业。- (300 点) N, K \leq 500
- (400 分)没有其他限制。
入力
输入是按以下格式从标准输入给出的。
N K A a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2 ... a_N b_N c_N d_N
出力
请输出可以达到的最大平均等级。
如果绝对或相对误差为
如果在 10^{-4} 如果低于此值则为正确答案。
入力例1
3 200 2804 2416 20 30 80 2269 80 20 80 2115 30 40 70
出力例1
2656.33333
通过如下操作可以将平均等级最大化。
- 首先,对社团成员施加压力,使其退出社团。 3 此时 E869120 的体力是 70 消耗。
- 接下来,对部员进行教育。 2 该值应乘以 6 这时 E869120 君在体力 120 消耗。
操作之后,剩下的部员只有 E869120 君和部员, 1、部員 2 他们各自的评分为 2804、2416、2749 。
入力例2
2 170 1 30 1 10 50 20 30 50 50
出力例2
47.66667
请注意,E869120 君也可以教育比自己评分更高的部员。
入力例3
4 300 4089 2800 20 30 40 3200 30 40 50 3600 30 50 60 4000 20 70 80
出力例3
4089.00000
如果进行了最优操作,E869120 君可以让其他所有部员退部, 1 实验俱乐部的成员将只剩下 E869120 君一人。
作者: 秋鳗 通过重新排列获得的序列