REF: OLP Việt Nam 2007

Có ~N~ trung tâm tư vấn (đánh số từ ~1~ đến ~N~), mỗi trung tâm có khả năng tư vấn về một số vấn đề. Trong một ngày làm việc, mỗi trung tâm chỉ tiếp được một số lượng khách nhất định. Một ngày cuối năm, có ~M~ khách (đánh số từ ~1~ đến ~M~), mỗi khách cần tư vấn về một vấn đề. Khách chỉ có thể đến trung tâm có khả năng tư vấn về vấn đề của mình.

Bạn hãy xác định giúp cần ít nhất bao nhiêu trung tâm hoạt động để có thể tư vấn cho tất cả các khách trong ngày cuối năm?

Input

Dòng thứ nhất chứa hai số nguyên ~M, N~ thỏa ~1 \le M \le 500, 1 \le N \le 50~.

Dòng thứ hai chứa ~M~ chữ cái in hoa liên tiếp, trong đó chữ thứ ~i~ mô tả vấn đề cần tư vấn của khách ~i~.

Dòng thứ ~j~ trong ~N~ dòng tiếp theo, ghi thông tin của trung tâm ~j~, gồm một số nguyên là lượng khách cho phép tư vấn trong ngày (không quá ~50~), sau đó là một dấu cách, tiếp sau là một dãy các chữ cái in hoa liền nhau mô tả dãy vấn đề mà trung tâm có thể tư vấn.

Dữ liệu vào đảm bảo bài toán có kết quả.

Output

In ra một dòng gồm ~M~ số, trong đó số thứ ~i~ là số hiệu xe xếp khách ~i~.

Samples

Sample Input 1

8 4
BNFQISNS
40 QIC
35 UPSF
45 FPHBU
15 WPSCNG

Sample Output 1

3