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~.

Xét ma trận ~A~ gồm ~m~ hàng và ~n~ cột, các hàng được đánh chỉ số từ ~1~ đến ~m~ theo thứ tự từ trên xuống dưới, các cột được đánh chỉ số từ ~1~ đến ~n~ theo thứ tự từ trái sang phải. Kí hiệu ~A(i, j)~ là giá trị của phần tử nằm giao giữa hàng ~i~ và cột ~j~ ~(1 \le i \le m; 1 \le j \le n)~.

Có hai thao tác rút gọn ma trận theo hàng và cột.

1. Thao tác rút gọn theo hàng: chọn hai hàng ~i~ và ~i + 1~ ~(1 \le i < m)~ mà tổng các phần tử trên hàng ~i~ bằng tổng các phần tử trên hàng ~i + 1~, việc rút gọn hàng ~i~ và ~i + 1~ theo các bước sau:

   • Bước 1: Thay đổi giá trị các phần tử trên hàng ~i~: ~A(i, j) = A(i ,j) + A(i + 1, j)~ với ~1 \le j \le n~;
   • Bước 2: Xóa hàng ~i + 1~ khỏi ma trận, khi đó số hàng của ma trận giảm đi một và các hàng được đánh chỉ số lại bắt đầu từ 1 từ trên xuống dưới.

2. Thao tác rút gọn theo cột: chọn hai cột ~j~ và ~j + 1~ ~(1 \le j < n)~ mà tổng các phần tử trên cột ~j~ bằng tổng các phần tử trên cột ~j + 1~, việc rút gọn cột ~j~ vả ~j + 1~ theo các bước sau:

   • Bước 1: Thay đổi giá trị các phần tử trên cột ~j~: ~A(i, j) = A(i, j) + A(i, j + 1)~ với ~1 \le i \le m~;
   • Bước 2: Xóa cột ~j + 1~ khỏi ma trận, khi đó số cột của ma trận giảm đi một và các cột được đánh chỉ số lại bắt đầu từ 1 từ trái sang phải;

Yêu cầu: Cho ma trận ~A~, hãy tìm một dãy các thao tác rút gọn để nhận được ma trận có số lượng phần tử là ít nhất.

Dữ liệu

Vào từ đầu vào chuẩn (không phải từ file RMAT.INP):

• Dòng đầu tiên chứa 2 số nguyên dương ~m~ và ~n~ là số hàng và số cột của ma trận;
• Dòng thứ ~i~ ~(1 \le i \le m)~ trong số ~m~ dòng tiếp theo chứa ~n~ số nguyên, mỗi số có giá trị tuyệt đối không vượt quá ~10^6~, số thứ ~j (1 \le j \le n)~ là giá trị ~A(i, j)~.

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 file RMAT.OUT) một số nguyên duy nhất là số lượng phần tử còn lại trong phương án thực hiện dãy các thao tác rút gọn tìm được.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thỏa mãn: ~m = 1~ và ~n \le 10~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn: ~m = 1~ và ~n \le 100~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thỏa mãn: ~m \times n \le 500~;
• ~10\%~ số test khác ứng với ~10\%~ số điểm của bài thỏa mãn: ~m \times n \le 5000~;
• ~10\%~ số test khác ứng với ~10\%~ số điểm của bài thỏa mãn: ~m \times n \le 10^6~.

Ví dụ

Input

3 5
1 2 3 4 5
5 4 3 2 1
4 -1 -1 -1 2

Output

6

Giải thích

Dãy các thao tác rút gọn như sau:

• Rút gọn hàng 1 và hàng 2 để nhận được ma trận:

6  6  6  6 6
4 -1 -1 -1 2

• Rút gọn cột 2 và cột 3 để nhận được ma trận:

6 12  6 6
4 -2 -1 2

• Rút gọn cột 1 và cột 2 để nhận được ma trận:

18  6 6 
 2 -1 2

Không thực hiện dược thêm thao tác rút gọn. Số lượng phần tử của ma trận thu được là ~6~.

Một công ty có ~n~ nhân viên, các nhân viên được đánh số từ ~1~ đến ~n~. Công ty đang chuẩn bị kỉ niệm 100 năm thành lập và dự định tổ chức nhiều hoạt động ngoại khóa. Một hoạt động được nhiều người mong đợi đòi hỏi phải chia ~n~ nhân viên thành hai nhóm. Qua thu thập thông tin, Ban tổ chức biết được ràng, nhân viên ~i~ không muốn cùng với nhân viên ~p_i~ ~(1 \le i \le n)~. Dựa trên yêu cầu của mỗi nhân viên, Ban tổ chức muốn tìm một cách chia ~n~ nhân viên thành hai nhóm mà nhân viên ~i~ khác nhóm với nhân viên ~p_i~. Trường hợp không tồn tại cách chia thỏa mãn, Ban tổ chức sẽ phải thuyết phục một số người chấp nhận cùng nhóm với người mà họ không muốn, thời gian để thuyết phục nhân viên ~i~ cùng nhóm với nhân viên ~p_i~ là ~w_i~.

Theo thông tin mà Ban tổ chức mới nhận được thì dữ liệu thu thập có thể chưa đầy đủ, có thể có thêm một cặp nhân viên ~(u, v)~ không muốn cùng một nhóm. Ban tổ chức đã đưa ra một danh sách gồm ~m + 1~ giả định: Giả định 0, không có thêm cặp nào; giả định thứ ~k~ ~(1 \le k \le m)~ là có thêm cặp nhân viên ~(u_k, v_k)~ không muốn cùng nhóm với nhau và nếu muốn cả hai nhân viên ~u_k~ và ~v_k~ đồng ý cùng nhóm thì phải mất thời gian thuyết phục cặp ~(u_k, v_k)~ là ~t_k~.

Yêu cầu: Với mỗi giả định, hãy giúp Ban tổ chức tính toán tổng thời gian thuyết phục ít nhất để có thể chia ~n~ nhân viên thành hai nhóm.

Dữ liệu

Vào từ đầu vào chuẩn (không phải file TEAMUP.INP):

• Dòng đầu chứa số nguyên dương ~n~ ~(n \le 10^5)~;
• Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa hai số nguyên dương ~p_i, w_i~ ~(p_i \le n; p_i \ne i; w_i \le 10^9)~;
• Dòng tiếp theo theo chứa số nguyên không âm ~m~ ~(m \le 10^5)~;
• Dòng thứ ~k~ trong số ~m~ dòng tiếp theo chứa ba số nguyên dường ~u_k, v_k, t_k~ ~(u_k, v_k \le n; u_k \ne v_k; u_k \ne p_{v_k}; v_k \ne p_{u_k}; t_k \le 10^9)~;

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 file TEAMUP.OUT) gồm ~m + 1~ dòng, mỗi dòng một số nguyên là tổng thời gian thuyết phục ít nhất lần lượt tương ứng cho từng giả định.

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn: ~m = 0, n \le 1000~ và dãy ~p_1, p_2, \dotsc, p_n~ là hoán vị của ~1, 2, \dotsc, n~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn: ~m = 0, n \le 1000~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm của bài thỏa mãn: ~m \le 1000, n \le 1000~;
• ~15\%~ số test khác ứng với ~15\%~ số điểm của bài thỏa mãn: dãy ~p_1, p_2, \dotsc, p_n~ là hoán vị của ~1, 2, \dotsc, n~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5
2 3
3 4
4 1
5 3
1 2
2
1 4 2
1 3 1

Output

1
2
2

Giải thích

• Giả định 0: Thuyết phục nhân viên 3 mất 1 đơn vị thời gian. Khi đó, có thể chia thành hai nhóm ~(1, 3, 4)~ và ~(2, 5)~.
• Giả định 1: Thuyết phục nhân viên 5 mất 2 đơn vị thời gian. Khi đó, có thể chia thành hai nhóm ~(1, 3, 5)~ và ~(2, 4)~.
• Giả định 2: Thuyết phục nhân viên 3 mất 1 đơn vị thời gian và thuyết phục cặp ~(1, 3)~ mất 1 đơn vị thời gian. Khi đó, có thể chia thành hai nhóm ~(1, 3, 4)~ và ~(2, 5)~.