미코는 N 개의 우리를 가진 돼지 농장에서 일한다. 그는 우리의 키를 가지고 있지 않아 우리를 열수가 없다.

고객들은 한사람씩 차례로 돼지우리의 키를 가지고 돼지를 사기위해 농장에 온다.

돼지를 파는 과정은 다음과 같다.

1. 고객이 도착한다.
2. 키가 있는 우리의 문을 모두 연다.
3. 미코는 열려진 우리에서 필요한 만큼의 돼지를 판다.
4. 만약 미코가 원한다면 열려진 우리에 있는 돼지들을 재 분배할 수 있다.

우리의 정원을 무한대로 가정하고 그 날 팔 수 있는 최대 돼지 수를 출력하는 프로그램을 작성 하시오.

입력

• 첫 줄에는 두 정수 N,M 이 주어진다.(1 <= N <= 1000, 1 <= M <= 100) 각각은 돼지우리 수 와 고객 수이다. 돼지우리는 1 에서 순차적으로 N 까지 번호가 부여되어 있고 , 고객은 1 에서 M 까지 부여되어 있다.
• 다음 줄은 M 개의 정수가 주어진다. 우리에 있는 돼지 수이다. 이 수는 0 보다 크고 1000 이하이다.
• 다음 N 줄은 A K1 K2 .. KA B 형식으로 A 는 고객이 가진 열쇠 수이고 다음 A 개의 수는 키를 가진 우리 번호로 크기 순으로 입력되고 마지막으로 이 고객이 필요한 돼지 수 B 가 주어진다. A,B 는 0 이 될수 있다.

출력

입출력 예

입력

3 3 
3 1 10 
2 1 2 2 
2 1 3 3
1 2 6

출력

7

출처:Croatia OI Final Exam -  2002