Ctudor (silent 'C') can't buy regular flowers because it's cruel to remove the reproductive organ of a plant for decorative purposes. Instead, he must buy orchids as those are interesting plants to grow. However, it is Valentine's Day and crappy grocery store orchids simply will not do, and Ctudor must buy good orchids from legendary plant collector Dennis. Dennis grows $N$ types of orchids (numbered from $1$ to $N$), and being a kind orchid collector offers $M$ deals to buy the orchids. Each deal will have a cost $C$ and can contain multiple of a certain type of orchid. Note that each deal can be used at most once.

Ctudor knows exactly which plants he wants and must determine the cheapest way to purchase them. Unfortunately, because his girl does not have enough lighting and plant space, Ctudor cannot buy extra orchids even if that lowers the cost.

Constraints

$1\le N,N_i,C_i,M\le 10$

$0\le D_i\le 100$

$0\le Q_i\le 10$

Input Specification

The first line will contain $N$ and $M$, the number of orchid types and the number of deals offered.

The next $N$ lines will contain $C_i$, the regular cost of orchid $i$.

The next $M$ lines will contain $N+1$ integers. The first integer is $D_i$, the total cost of the deal and the next $N$ integers are $Q_i$, the quantity of orchid $i$ that are included in the deal.

The final line will contain $N$ space-separated integers $N_i$, the $i^{\text{th}}$ integer representing the quantity of orchid $i$ that needs to be purchased.

Output Specification

The lowest possible cost to buy all the orchids.

Sample Input 1

2 2
2
5
5 3 0
10 1 2
3 2

Sample Output 1

14

Sample Input 2

3 2
2
3
4
4 1 1 0
9 2 2 1
1 2 1

Sample Output 2

11