Glass beads

Time Limit: 5000 ms

Memory Limit: 65535 ms

Description

Rose has a shop which sell beads,one day ,there comes several children,they want to buy some glass beads,Rose has some boxes to place the glass beads.Rose think all the children are lovely .so she want to know their name and make friends with them so she thinks a strategy to sell the glass beads : there are M children and N boxes, every child should choose a paper before choosing some glass beads from some boxes, there is a string on the paper ,and the number of the boxes he can choose from is the number of vowel letters of the string(every string has vowel letters) ,and the location of the vowel letters decide which boxes he can choose (for example “all”there is a vowel letter in 1-th location ,so he can choose from the first boxes ),the location of the first letter of the string is 1,if the location is more than the number of the boxes N,then should mod N(if equal to 0 then choose from the N-th box ). After a child chooses beads and before another child chooses Rose can change the beads between boxes ,Rose want to know the most number of glass beads she can sold in this condition .So she want you to write a program to solve this problem.

Input

The first line of input contains two integers M and N, 1 <= M <= 500, 1 <= N <= 100, number of boxes and number of children. Beads boxes are numbered from 1 to M and children are numbered from 1 to N. The next line contains M integeres, for each boxes initial number of beads. The number of beads in each boxes is greater or equal to 0 and less or equal to 500. The next N lines contains records about the children in the following form ( record about the i-th children is written in the (i+2)-th line): sting Q is the name of the children and that he wants to buy P beads at most. Numbers P can be equal to 0.

Output

The only line of the output should contain the maximum number of sold beads.

Sample Input

2 2
3 6
ewro 3
eshdv 5
4 5
3 4 6 5
initial 3
number 6
house 5
mark 5
next 4

Sample Output

8
13

Hint

Source

MengShunMei

提交代码