Optimal Milking optimilk.txt FJ's N (1 <= N <= 100) cows are very special. Not only they are the smartest cows, but they produce the best milk ever tasted -- in two different flavors. Each one produces both regular white milk and also delicious, rich, chocolate milk! FJ needs to obtain at least L (1 <= L <= 100) litres of each type of milk. Help him milk the cows as efficiently as possible. You are given the time cow i requires to make 1 liter of white milk (1 <= w_i <= 100) and likewise chocolate milk (1 <= c_i <= 100). You must find a strategy so that after finishing milking, FJ has at least L litres of both flavors of milk, and the total milking time is minimized. A cow can't produce both sorts of milk at the same time, though she can produce an integer quantity of one kind of milk and then switch to producing an integer quantity of the other. FJ milks his cows simultaneously using high-tech milking equipment which always milks an even number of liters from a cow. PROBLEM NAME: optimilk INPUT FORMAT: * Line 1: Two space separated integers, N and L * Lines 2..N+1: Line i+1 contains two space-separated integers, w_i and c_i SAMPLE INPUT: 3 20 1 1 2 4 1 6 OUTPUT FORMAT: * Line 1: A single integer that is the minimal time FJ needs to obtain L liters of each sort of milk. SAMPLE OUTPUT: 18 OUTPUT DETAILS: The minimum amount of time needed is 18. Cow #1 makes 0 liters of white milk and 18 liters of chocolate milk. She finishes in 0 * 1 + 18 * 1 = 18 minutes. Cow #2 makes 2 liters of white milk and 2 liters of chocolate milk. She finishes in 2 * 2 + 2 * 4 = 12 minutes. Cow #3 makes 18 liters of white milk and 0 liters of chocolate milk. She finishes in 18 * 1 + 6 * 0 = 18 minutes. The minimum time FJ needs to milk his cows is maximum(18, 12, 18) = 18 minutes.