17854번 - Cheese, If You Please 다국어

The “We Cut The Cheese” specialty food store sells specialized blendings of cheeses. For example, their Italian Blend is made up of 50% provolone, 30% mozzarella and 20% parmesan, while their African Safari is made up of 74% domiati, 25% areesh with just a hint (1%) of bokmakiri. You started working at the store as a cheese blend taster, but two years and 45 pounds later you have worked your way up to head of the accounting office. Every week the store gets various shipments of cheeses, depending on the time of year, market price and other factors. Given these amounts and the percentages required for each cheese blend, you are asked every week to determine the optimal use of these cheeses to maximize profit. When the store just made a few different cheese blends this could be done by hand, but with business expanding faster than a cheese souffle, the number of blends has also grown to the point where a program is now needed to determine the optimal use of the cheese shipments. So the question is: Are you gouda-nough to write such a program?

Input starts with a line containing two positive integers n m (1 ≤ n, m ≤ 50), where n is the number of types of cheese used to make the cheese blends and m is the number of different cheese blends offered by the store. The next line contains n integers w₁ w₂ . . . w_n (0 ≤ w_i ≤ 500), where w_i is the number of pounds of cheese type i that the store has on-hand. Following this are m lines of the form p₁ p₂ p₃ . . . p_n t (0.0 ≤ p_i ≤ 100.0, 0.0 ≤ t ≤ 10.0), where pi indicates the percentage of cheese i found in the blend, and t is the profit per pound for the blend.

Output the maximum profit that can be obtained for the given pounds of cheese, blending percentages and profits, assuming all of the blended cheeses get sold. Round your answer to the nearest penny.