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 types of orchids (numbered from to ), and being a kind orchid collector offers deals to buy the orchids. Each deal will have a cost 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.
The first line will contain and , the number of orchid types and the number of deals offered.
The next lines will contain , the regular cost of orchid .
The next lines will contain integers. The first integer is , the total cost of the deal and the next integers are , the quantity of orchid that are included in the deal.
The final line will contain space-separated integers , the integer representing the quantity of orchid that needs to be purchased.
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
Sample Input 2
3 2 2 3 4 4 1 1 0 9 2 2 1 1 2 1
Sample Output 2