Nam vừa đoạt giải quán quân trong một kỳ thi lập trình danh giá. Ban tổ chức trao thưởng thông qua một trò chơi như sau. Có n thẻ xếp trên một hàng, được đánh số thứ tự từ 1 đến n tử trái sang phải, trên thẻ thứ i (1 <= i <= n) có hai thông tin:

• Nhãn ci là một xâu kí tự chỉ gồm các kí tự chữ cái la tinh in hoa (từ 'A' đến 'Z');

• Số may mắn pi là một số nguyên dương.

Ban tổ chức cũng công bố m cặp số may mắn và cho phép Nam thực hiện một hoặc nhiều bước chọn các thẻ. Ban đầu, Nam chọn một thẻ bất kỳ, điểm nhận được là số may mắn trên thẻ đó. Mỗi bước tiếp theo, Nam thực hiện theo một trong hai cách sau:

1. Trong các thẻ ở phía bên phải thẻ hiện tại, chọn một thẻ có nhãn là một xâu mà có thể nhận được bằng cách xóa từ xâu là nhãn của thẻ hiện tại một số kí tự cuối cùng (ít nhất một kí tự). Số điểm nhận được thêm bằng số may mắn trên thẻ mới chọn;

2. Trong các thẻ ở phía bên phải thẻ hiện tại, chọn một thẻ mà số may mắn trên thể này và số may mắn trên thẻ hiện tại Tà một cặp số may mắn. Cụ thể, nếu số may mắn trên thẻ hiện tại là pi và số may mắn trên thẻ mới chọn là pi thì cặp số (pi, pj)) hoặc (pj, pi) phải là một trong các cặp số may mắn mà Ban tổ chức đã công bố. Số điểm nhận được thêm bằng số may mắn trên thẻ mới chọn.

Sau một số bước chọn, nếu Nam không chọn được nữa thì số tiền thưởng bằng tổng điểm tích lũy được.

Yêu cầu: Hãy giúp Nam tỉm cách chọn các thẻ để đạt được tổng số tiền thưởng là lớn nhất.

Dữ liệu: Vào từ file văn bản BONUS.INP:

• Dòng thứ nhất chứa số nguyên dương n và số nguyên không âm m

• Tiếp theo là n cấp dòng mô tả thông tin trên thẻ. Cặp dòng thứ i (1 <= i <= n) có dòng thứ nhất chứa nhãn và dòng thứ hai chứa số may mắn của thẻ thứ i.

• Mỗi dòng trong số m dòng cuối cùng chứa hai số nguyên dương mô tả một cặp số may mắn.

Các thẻ có thể có nhãn giống nhau và tổng số các kí tự của các nhãn trên các thẻ không vượt quá 10^6. Các số may mắn có giá trị không vượt quá 10^5. Các số may mắn có giá trị không vượt quá 105. Các số trên cùng một dòng cách nhau bởi dầu cách.

Kết quả: Ghi ra file văn bản BONUS.OUT một số nguyên duy nhất là tổng tiền thưởng lớn nhật chọn được.

Ràng buộc:

• Có 40% số test ứng với 40% số điểm của bải thoa mãn: n ≤ 100, nhân trên các thẻ có độ dài không vượt quá 100 và m ≤ 100

• 40% số test khác ứng với 40% số điểm của bài thỏa mãn: n ≤ 3 x 10^5 và m = 0;

• 20% số test còn lại ứng với 20% số điểm của bải thoa mãn: n ≤ 3 x 10^5 và m ≤ 3 x 10^5.

Ví dụ:

Input:

4 1
ABA
5
BC
10
AB
5
A
6
6 10

Output:

16