Feed Factories cowfact.X Farmer John has discovered that villainous feed salesmen have been ripping him off by charging him more than the market price of M cowbucks per pound of feed! In order to prevent this from ever being a problem again, he plans to purchase enough feed factories to be entirely self-sufficient and never have to purchase from a salesman. Farmer John currently uses K pounds of feed (1 <= K <= 100) per day on his farm. He has surveyed a group of N (2 <= N <= 100) feed factories, determining for each the daily productivity P_i (1 <= P_i <= 100) and a daily maintenance cost C_i (1 <= C_i <= 100). FJ is a business-savvy guy, and he wants to make his business as efficient as possible. FJ measures the efficiency of a business by the formula (total profits) / (total productivity). Since he will sell all his feed at the market price of M (1 <= M <= 100) cowbucks/pound, the total profit is M * sum(P_i) - sum(C_i) Hence the efficiency is M - (sum(C_i) / sum(P_i)) (we don't subtract the M*K cost of the feed FJ uses because he would have to pay for it anyway). FJ only produces R (2 <= R <= 100,000) cowbucks per day in profit from his farm, and so he will not accept expenditures greater than that in case the cow feed industry fails. Help him determine the maximum efficiency his new business can achieve. PROBLEM NAME: cowfact INPUT FORMAT: * Line 1: Four space-separated integers: N, K, and M, and R * Lines 2..N+1: Line i describes factor i with two space-separated integers: C_i and P_i SAMPLE INPUT: 5 54 7 100 10 10 20 18 30 25 40 22 50 30 OUTPUT FORMAT: * Line 1: The positive integer that is the truncated product of 1,000 and the maximum efficiency of FJ's business with a minimum total productivity of K if that value is positive, or -1 if the maximum efficiency is negative. SAMPLE OUTPUT: 5666 OUTPUT DETAILS: FJ takes the first 4 factories, for a total productivity of 75 and a total cost of 100, so the efficiency is 7 - 4/3 = 5.66666... Note that we cannot buy the first three factories and the 5th, which would give a slightly higher efficiency, due to FJ's limited value of R. He cannot succeed using only the first three factories because K is too big.