“Farm Game” is one of the most popular games in online community. In the community each player has a virtual farm. The farmer can decide to plant some kinds of crops like wheat or paddy, and buy the corresponding crop seeds. After they grow up, The farmer can harvest the crops and sell them to gain virtual money. The farmer can plant advanced crops like soybean, watermelon or pumpkin, as well as fruits like lychee or mango.
Feeding animals is also allowed. The farmer can buy chicken, rabbits or cows and feeds them by specific crops or fruits. For example, chicken eat wheat. When the animals grow up, they can also “output” some products. The farmer can collect eggs and milk from hens and cows. They may be sold in a better price than the original crops.
When the farmer gets richer, manufacturing industry can be set up by starting up some machines. For example, Cheese Machine can transfer milk to cheese to get better profits and Textile Machine can spin cony hair to make sweaters. At this time, a production chain appeared in the farm.
Selling the products can get profits. Different products may have different price. After gained some products, the farmer can decide whether to sell them or use them as animal food or machine material to get advanced products with higher price.
Jack is taking part in this online community game and he wants to get as higher profits as possible. His farm has the extremely high level so that he could feed various animals and build several manufacturing lines to convert some products to other products.
In short, some kinds of products can be transformed into other kinds of products. For example, 1 pound of milk can be transformed into 0.5 pound of cheese, and 1 pound of crops can be transformed into 0.1 pound of eggs, etc. Every kind of product has a price. Now Jack tell you the amount of every kind of product he has, and the transform relationship among all kinds of products, please help Jack to figure out how much money he can make at most when he sell out all his products.
Please note that there is a transforming rule: if product A can be transformed into product B directly or indirectly, then product B can never be transformed into product A, no matter directly or indirectly.
The input contains several test cases. The first line of each test case contains an integers N (N<=10000) representing that there are N kinds of products in Jack’s farm. The product categories are numbered for 1 to N. In the following N lines, the ith line contains two real numbers p and w, meaning that the price for the ith kind of product is p per pound and Jack has w pounds of the ith kind of product.
Then there is a line containing an integer M (M<=25000) meaning that the following M lines describes the transform relationship among all kinds of products. Each one of those M lines is in the format below:
K a0, b1, a1, b2, a2, …, bk-1, ak-1
K is an integer, and 2×K-1 numbers follows K. ai is an integer representing product category number. bi is a real number meaning that 1 pound of product ai-1 can be transformed into bi pound of product ai.
The total sum of K in all M lines is less than 50000.
The input file is ended by a single line containing an integer 0.
For each test case, print a line with a real number representing the maximum amount of money that Jack can get. The answer should be rounded to 2 digits after decimal point. We guarantee that the answer is less than 10^10.
2 1 0.5 2
2 1 0.8 2
- 博客 在中国程序员是青春饭吗？
- 博客 程序员请照顾好自己，周末病魔差点一套带走我。
- 博客 技术大佬：我去，你写的 switch 语句也太老土了吧
- 博客 和黑客斗争的 6 天！
- 博客 上班一个月，后悔当初着急入职的选择了
- 博客 女程序员，为什么比男程序员少？？？
- 博客 总结了 150 余个神奇网站，你不来瞅瞅吗？
- 博客 副业收入是我做程序媛的3倍，工作外的B面人生是怎样的？
- 博客 如果你是老板，你会不会踢了这样的员工？
- 博客 我入职阿里后，才知道原来简历这么写
- 博客 外包程序员的幸福生活
- 博客 优雅的替换if-else语句
- 博客 深入剖析Springboot启动原理的底层源码，再也不怕面试官问了！
- 博客 离职半年了，老东家又发 offer，回不回？
- 博客 2020阿里全球数学大赛：3万名高手、4道题、2天2夜未交卷
- 博客 男生更看重女生的身材脸蛋，还是思想？
- 博客 为什么程序员做外包会被瞧不起？
- 博客 当HR压你价，说你只值7K，你该怎么回答？
- 博客 面试：第十六章：Java中级开发（16k）
- 博客 面试阿里p7，被按在地上摩擦，鬼知道我经历了什么？
- 博客 你期望月薪4万，出门右拐，不送，这几个点，你也就是个初级的水平
- 博客 面试了一个 31 岁程序员，让我有所触动，30岁以上的程序员该何去何从？
- 博客 大三实习生，字节跳动面经分享，已拿Offer
- 博客 程序员垃圾简历长什么样？
- 博客 《Oracle Java SE编程自学与面试指南》最佳学习路线图2020年最新版（进大厂必备）
- 博客 《Oracle Java SE编程自学与面试指南》最佳学习路线图（2020最新版）
- 博客 字节跳动面试官竟然问了我JDBC？
- 博客 面试官：你连SSO都不懂，就别来面试了
- 博客 终于，月薪过5万了！
- 博客 自从喜欢上了B站这12个UP主，我越来越觉得自己是个废柴了！