HELPBOB - Help Bob

Bob loves Pizza but is always out of money. One day he reads in the newspapers that his favorite pizza restaurant, Alfredo's Pizza Restaurant, is running a competition: they will donate a big pizza to the first person who will tell them the lowest price per area that can be achieved by buying any of the pizzas at most once. "That task is easy!", thinks Bob, "For each pizza I just calculate the average price and the lowest quotient will be the answer.".

Unfortunately the problem is a bit more complicated: with some pizzas Alberto gives out discount coupons for getting another pizza cheaper and even worse, those coupons can be combined. The pizzas have to be bought one after the other, and it is not possible to use a coupon to get a discount retrospectively for a pizza which has already been bought. Can you help Bob to become the first to solve this task and to get a pizza for free?

Input

The input file contains several test cases. Each test case starts with a number m, the number of pizzas Alfredo offers. Input is terminated by m=0. Otherwise, 1 ≤ m ≤ 15. Then follow m lines describing the pizzas. Each of those following lines describes pizza i (1 ≤ i ≤ m) and starts with 3 integer numbers pi, ai and ni specifying the price of the pizza, its area and the number of discount coupons you get when buying it, 1 ≤ pi ≤ 10000, 1 ≤ ai ≤ 10000 and 0 ≤ ni < m. Then follow ni pairs of integer numbers xi,j and yi,j specifying the index xi,j (1 ≤ xi,j ≤ m, xi,j ≠ i) of the pizza you get a discount coupon for and the discount in percentage terms yi,j (1 ≤ yi,j ≤ 50) you get when buying pizza xi,j. You may assume that for each i the values xi,j are pairwise distinct.

Output

For each test case print one line containing the lowest price per area that can be achieved by buying any of the pizzas at most once. Round this number to 4 places after the decimal point. Note that you can combine an arbitrary number of discount coupons: for a pizza with price 10 and two rabatt coupons for that pizza with a 50 and a 20 on it, you would only have to pay 10 * 0.8 * 0.5 = 4 monetary units.

Example

Input:
1
80 30 0
2
200 100 1 2 50
200 100 0
5
100 100 2 3 50 2 50
100 100 1 4 50
100 100 1 2 40
600 600 1 5 10
1000 10 1 1 50
0

Output:
2.6667
1.5000
0.5333

Added by:Adrian Kuegel
Date:2008-07-12
Time limit:1.783s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:University of Ulm Local Contest 2008

hide comments
2019-09-15 10:03:19
*props to the setter*
Good problem.
2017-04-01 05:11:04 AMIT KUMAR YADAV
Happy to help Bob :)
2016-05-20 16:14:51 dev
(2^n)*n^2 with getchar_unlocked !!

Last edit: 2016-05-20 16:15:35
2015-12-12 20:41:22 xxbloodysantaxx
Round Down to 4 digits . I didn't read that !!
Morover people with O(N^2 * 2 ^n ) , you can optimize it easily with the help of some precomputation .

2015-03-22 06:13:42 Sudharsansai
O(n*n*(2^n)) with printf and scanf in C++ can get AC easily

Last edit: 2015-03-22 06:15:05
2014-10-28 15:43:28 Varun Vohra
my O(n * n * 2^n) complexity giving TLE..
Is this complexity fine or i have to do some opimizations in my algo?
2014-10-15 23:23:17 Aditya Paliwal
Got AC! Had to write iteratively rather than recursively. Learnt sooo much from this problem :D AWESOME! Also can anybody tell me how best solution is 1 sec? I barely made it thought the time limit!

Last edit: 2014-10-16 00:05:27
2014-01-22 10:01:06 PubLic_AvenGeR
Nice Problem !!
I needed to lower the constant factor to get accepted.
2013-12-31 03:30:54 Ghost Of Perdition
can anyone please explain the third case in the sample
i think buying the first four pizzas in orded 1 3 2 4 will give better answer
2011-09-15 05:20:21 Ravi Kiran
@Adrian:
I agree. Tried again, with a solution of better constant and scanf usage, and made a much better time.
Hope it helps.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.