## ICPC ECNA 2019 C - Cheese, If You Please

View as PDF

Points: 25
Time limit: 1.0s
Memory limit: 1G

Problem type
##### ICPC East Central NA Regional Contest 2019, Problem C

The "We Cut The Cheese" specialty food store sells specialized blendings of cheeses. For example, their Italian Blend is made up of provolone, mozzarella and parmesan, while their African Safari is made up of domiati, areesh with just a hint of bokmakiri. You started working at the store as a cheese blend taster, but two years and 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 Specification

Input starts with a line containing two positive integers , where is the number of types of cheese used to make the cheese blends and is the number of different cheese blends offered by the store. The next line contains integers , where is the number of pounds of cheese type that the store has on-hand. Following this are lines of the form , , where indicates the percentage of cheese found in the blend, and is the profit per pound for the blend. Percentages are given with one decimal place, profits are given with two decimal places.

#### Output Specification

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.

#### Sample Input 1

3 2
100 150 100
50.0 50.0 0.0 3.20
0.0 50.0 50.0 2.80

#### Sample Output 1

920.00

#### Sample Input 2

3 2
100 150 100
50.0 50.0 0.0 3.20
0.0 40.0 60.0 2.80

#### Sample Output 2

1000.00