题目描述

小明一共有 $n$ 项作业，第 $i$ 项作业要在时间 $d_i$ 之前完成，小明完成第 $i$ 项作业需要 $b_i$ 的时间，对于小明来说，喝奶茶可以提高工作效率，但是奶茶对于不同的作业功效都是不同的，你可以认为，小明在做第 $i$ 项作业期间，每喝 $1ml$ 的奶茶，他完成第 $i$ 项作业所需要的时间就会减少 $a_i$，当然，奶茶还不至于神奇到有时光倒流的功能。

现在，小明想知道，他要按时完成所有作业最少要喝的奶茶。

输入格式

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

接下来 $n$ 行每行三个正整数 $a_i$，$b_i$，$d_i$。

输出格式

输出一个小数，表示小明要按时完成所有作业最少要喝奶茶的毫升数。（保留两位小数）

样例

输入样例

2
20 50 100
10 100 50

输出样例

5.00

数据范围与提示

对于 $20\%$ 的数据，$n≤10$，对于所有 $i$ 满足 $d_i≤100$ 且 $a_i=1$。

对于 $40\%$ 的数据，$n≤3000$。

对于 $100\%$ 的数据，$1≤n≤200000$，$a_i,b_i,d_i≤10^6$。

分类标签

(无)