UOJ Logo

NOI.AC

#88. 蔬菜

统计

题目描述

​ 老虎和蒜头是好朋友。

​ 老虎最近开始承担起了给森林学校食堂采购货物的工作。森林学校需求 $ n $ 种蔬菜,在学校食堂里第 $ i $ 种蔬菜还有 $ c_i $ 千克的库存,购买第 $ i $ 种蔬菜 $ d_i $ 千克会花费 $ p_i d_i^2 + q_i d_i + r_i $ 元(买少了会被提高价格,买多了难买还要额外花钱)。现在老虎有 $ m $ 元,蒜头想要知道,不妨假设最少的那种蔬菜的数量是 $ w $ 千克,那么 $ w $ 的最大值是多少。

输入格式

​ 第一行共一个正整数 $ n $ 。

​ 接下来的 $ n $ 行,第 $ i $ 行包括四个数 $ c_i, p_i, q_i, r_i $ 。

​ 接下来一行一个正整数 $ m $ 。

输出格式

​ 输出共一行一个实数 $ w $ ,你只要保证绝对或相对误差不超过 $ 10^{-6} $ 即可。

样例

样例一

input

3
3 100000 100000 100000
1 20 0 0
0 0 10 10
120

output

3.000000000000

explanation

考虑当 $ w = 3 $ 时,第一种蔬菜无需购买,因此会花费 $ 0 $ 元;第二种蔬菜需要购买 2 千克,因此花费 $ 20 \times 2 \times 2 = 80 $ 元;第三种蔬菜需购买 3 千克,因此会花费 $ 10 \times 3 + 10 = 40 $ 元。

当 $ w > 3 $ 时,第一种蔬菜库存不足,需要购买。因此至少有 $ 100121 $ 元才能使得 $ w > 3 $。

样例二

见样例数据下载。

数据范围及限制

对于 100% 的数据, $ n \le 10^5, 0 \le c_i \le 10^6, p_i + q_i \ge 1, 0 \le p_i, q_i, r_i, m \le 10^{14} $ 。

对于 30% 的数据,$ n = 1 $ 。

对于另外 30% 的数据,$ p_i = 0 $ 。

时间限制: 1s

空间限制: 512MB

样例数据下载