QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB
[0]

# 3611. Smoothie Stand

Statistics

Olivia runs a very famous and profitable smoothie stand. On any given day, she will always sell out (that is, she will sell as many smoothies as she has ingredients to make), regardless of what smoothie recipe she offers. Therefore, to simplify things, she has decided she will only make one type of smoothie per day. Now she has come to you to help her decide which of her recipes she should use today, given the ingredients she has on hand and the sale price of each type of smoothie.

Input

The first line contains two integers k and r, separated by a space. The value k is the number of different ingredients Olivia uses in her smoothies and r is the number of different recipes she makes. You may assume 1k100000, 1r100000, and 1kr100000. The second line contains k integers, which represent the amount of each ingredient she currently has on hand. This is followed by r lines, each of which represents a recipe. On each such line, the first k space-separated integers represent the amount of each ingredient used in that recipe. This is followed by one integer representing the price charged for one smoothie of that recipe.

You may assume that all values, except possibly k and r, are nonnegative integers less than or equal to 104. It is guaranteed that each recipe uses at least one ingredient.

Output

Output the largest total sales revenue that can be obtained by choosing a single recipe and making as many of that recipe as possible.

Examples

Sample Input 1

3 2
5 10 10
1 4 1 5
3 3 3 3

Sample Output 1

10

Sample Input 2

4 3
10 9 8 7
0 1 2 4 10
3 1 1 2 4
2 0 3 3 5

Sample Output 2

12