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 \le i \le n)~ có hai thông tin:

• Nhãn ~c_i~ là một xâu kí tự gồm các kí tự chữ cái la tinh in hoa (từ A đến Z);
• Số may mắn ~p_i~, 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 là một cặp số may mắn. Cụ thể, nếu số may mắn trên thẻ hiện tại là ~p_i~ và số may mắn trên thẻ mới chọn là ~p_j~ thì cặp số ~(p_i, p_j)~ hoặc ~(p_j, p_i)~ 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ừ đầu vào chuẩn (không phải từ file 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 \le i \le 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ố trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra đầu ra chuẩn (không phải ra file 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 tương ứng với ~40\%~ số điểm của bài thỏa mãn: ~n \le 100~, nhãn trên các thẻ có độ dài không vượt quá 100 và ~m \le 100~;
• ~40\%~ số test khác ứng với ~40\%~ số điểm của bài thảo mãn: ~n \le 3\times 10^5~ và ~m = 0~.
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài thỏa mãn: ~n \le 3 \times 10^5~ và ~m \le 3 \times 10^5~.

Ví dụ

Input

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

Output

16

Giải thích

Nam chọn thẻ thứ 2 rồi chọn tiếp thẻ thứ 4 bằng cách sử dụng cặp số may mắn ~(6, 10)~ đẻ nhận được tổng tiền thưởng là 16.

Một cách chọn khác cũng được tổng tiền thưởng là 16 bằng cách chọn lần lượt các thẻ ~1, 3, 4~.