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 ~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 soufflé, 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 ~n\ m~ (~1 \le n,m \le 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_1\ w_2 \dots w_n~ (~0 \le w_i \le 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_1\ p_2\ p_3 \dots p_n\ t~ (~0.0 \le p_i \le 100.0~, ~0.0 \le t \le 10.0~), where ~p_i~ indicates the percentage of cheese ~i~ found in the blend, and ~t~ 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