Độ Đẹp Của Xâu Đối Xứng

Bạn được tặng $k$ xâu, mỗi xâu có độ dài $n$. Xâu thứ $i$ là $s_i$ và có độ đẹp $a_i$ (có thể âm).

Bạn được chọn một số (có thể không chọn, có thể chọn tất cả) trong các xâu đã cho và ghép chúng lại theo một thứ tự tuỳ ý để tạo thành một xâu mới. Mỗi xâu chỉ được dùng nhiều nhất một lần. Tổng độ đẹp của xâu ghép được là tổng các $a_i$ của những xâu được chọn.

Hãy tìm tổng độ đẹp lớn nhất của một xâu ghép được sao cho xâu đó là xâu đối xứng (đọc xuôi và đọc ngược giống nhau).

Lưu ý: xâu rỗng cũng là một xâu đối xứng, nên đáp án không bao giờ âm — kể cả khi tất cả $a_i$ đều âm thì ta luôn có thể tạo ra xâu rỗng với độ đẹp $0$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $k$ và $n$ — số xâu và độ dài mỗi xâu.
• $k$ dòng tiếp theo, dòng thứ $i$ chứa xâu $s_i$ gồm $n$ chữ cái latin in thường và một số nguyên $a_i$ — độ đẹp của xâu, cách nhau bởi dấu cách.

Một số xâu có thể trùng nhau, và các xâu giống nhau vẫn có thể có độ đẹp khác nhau.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng độ đẹp lớn nhất.

Ràng buộc

• $1\le k,n\le {10}^5$ và $n·k\le {10}^5$
• $-{10}^4\le a_i\le {10}^4$

Ví dụ