Problem H
A Production Problem

You run a somewhat successful materials manufacturing company. However, you wish you ran a very successful materials manufacturing company. To get your company to the next level, you need to optimize your production strategies to maximize your profits and, therefore, seize the means of production.

Your company produces multiple different alloys from combinations of metals. Each of the alloys that you manufacture requires different metals and you can sell it for a different price. Also, your company has a limited quantity of each of the metals on hand, so some alloys are more profitable to manufacture than others. You need to determine how much of each product to manufacture, to maximize your company’s profits and seize the means of production!

Input

The first line of the input contains $2$ integers, $m$ and $n$ ($1 \le m,n \le 50$). $m$ is the number of metals that your company has and $n$ is the number of alloys you offer. The next line of input consist of $m$ positive integers, each representing the number of pounds of each metal that your company has. The final $n$ lines of input consist of $m + 1$ real values, representing the percentage of each of the metals required to produce one pound of that alloy, and the profit gained from producing that pound.

Output

Output the maximum profit you can achieve given the metals and alloys at your disposal. Print the answer with exactly two digits after the decimal point.

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

920.00