Hạo vừa chiến thắng trong một cuộc thi tin học quốc tế và được trao một cơ hội để nhận phần thưởng thông qua một thử thách đặc biệt. Trên bàn có \(n\) viên đá quý được sắp xếp theo hàng, mỗi viên đá được đánh số từ \(1\) đến \(n\), theo thứ tự từ trái sang phải. Mỗi viên đá thứ \(i\) \((1 \le i \le n)\) có hai đặc điểm:

• Tên gọi: Là một chuỗi ký tự gồm các chữ cái Latinh in hoa (từ \(A\) đến \(Z\)), đại diện cho tên của viên đá quý.
• Giá trị: Là một số nguyên dương, thể hiện giá trị của viên đá.

Ban tổ chức cũng cung cấp một danh sách \(m\) cặp giá trị đặc biệt và cho phép Hạo thực hiện các bước lựa chọn đá quý dựa trên những quy tắc sau. Ban đầu, Hạo có thể chọn bất kỳ viên đá nào, và giá trị đầu tiên Hạo nhận được sẽ bằng giá trị của viên đá đó. Sau đó, trong mỗi bước tiếp theo, Hạo có thể tiếp tục chọn đá quý theo một trong hai cách sau:

1. Cách 1: Trong số các viên đá nằm bên phải viên đá hiện tại, Hạo có thể chọn một viên có tên gọi là một phần rút gọn từ tên của viên đá hiện tại. Điều này có nghĩa là tên của viên đá mới phải là chuỗi được tạo ra bằng cách xóa bớt một số ký tự cuối cùng từ tên của viên đá hiện tại. Khi đó, Hạo nhận thêm giá trị bằng giá trị của viên đá mới chọn.

2. Cách 2: Hạo có thể chọn một viên đá ở phía bên phải mà giá trị của nó tạo thành một cặp giá trị đặc biệt với viên đá hiện tại. Cụ thể, nếu viên đá hiện tại có giá trị là \(v_i\) và viên đá mới có giá trị là \(v_j\), thì cặp số \((v_i, v_j)\) hoặc \((v_j, v_i)\) phải nằm trong danh sách các cặp giá trị đặc biệt mà Ban tổ chức đã công bố. Khi đó, Hạo nhận thêm giá trị bằng giá trị của viên đá mới chọn.

Hạo tiếp tục lựa chọn cho đến khi không còn có thể chọn thêm viên đá nào nữa. Khi đó, tổng giá trị mà Hạo thu được sẽ là phần thưởng của cậu.

Nhiệm vụ: Hãy tìm cách giúp Hạo lựa chọn các viên đá sao cho tổng giá trị mà cậu có được là cao nhất.

Dữ liệu vào

• 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 đá quý. 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 giá trị của viên đá quý 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 đá quý đặc biệt.

Các viên đá quý có thể có tên giống nhau và tổng số các kí tự của các tên đá quý không vượt quá \(10^6\). Các viên đá quý 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.

Dữ liệu ra

• Một số nguyên duy nhất là tổng giá trị lớn nhất chọn được.

Ràng buộc

• 40% số test tương ứng 40% số điểm có \(n,m \le 100\), tên các đá quý có độ dài không quá \(100\)
• 40% số test khác ứng với 40% số điểm của bài thỏa 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,m \le 3 \times 10^5\)

Input 1

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

Output 1

16

Giải thích

Hạo chọn viên đá thứ \(2\) rồi chọn tiếp viên đá thứ \(4\) bằng cách sử dụng cặp số đặc biệt \((6,10)\) để nhận được tổng giá trị thưởng là \(16\).

Một cách chọn khác cũng được tổng giá trị thưởng là \(16\) bằng cách chọn lần lượt các viên \(1,3,4\)