Ký Ức Vụn Vỡ

Giáo sư Gilderoy Lockhart thầy giáo Phòng Chống Nghệ Thuật Hắc Ám tại Hogwarts - vừa thực hiện một Bùa Xóa Trí Nhớ (Memory Charm) thất bại thảm hại. Thay vì xóa trí nhớ của mục tiêu, lời nguyền đã phản ngược lại và phá vỡ chính ký ức của Lockhart thành $N$ mảnh vỡ.

Mỗi mảnh ký ức $i$ mang một ký tự đặc trưng $c_i$ (chữ cái thường Latin) và một giá trị cảm xúc $w_i$. Các mảnh ký ức được liên kết với nhau theo $M$ kết nối một chiều, tạo thành một đồ thị có hướng không chu trình (DAG): nếu có kết nối từ mảnh $u$ đến mảnh $v$, thì mảnh $u$ là tiền đề để nhớ lại mảnh $v$.

Giáo sư Dumbledore muốn giúp Lockhart khôi phục lại một chuỗi ký ức có ý nghĩa. Một chuỗi ký ức là một đường đi trong đồ thị (theo chiều các cạnh). Chuỗi ký ức được coi là có ý nghĩa nếu dãy ký tự đặc trưng của các mảnh trên đường đi tạo thành một xâu đối xứng (palindrome).

Dumbledore muốn tìm chuỗi ký ức có ý nghĩa với tổng giá trị cảm xúc lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $M$ ($1\le N\le 1500$, $0\le M\le 5000$) — số mảnh ký ức và số kết nối.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa một ký tự $c_i$ và một số nguyên $w_i$ ($1\le w_i\le {10}^9$) — ký tự đặc trưng và giá trị cảm xúc của mảnh ký ức thứ $i$.
• $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ ($1\le u,v\le N$, $u\ne v$) — biểu thị một kết nối từ mảnh $u$ đến mảnh $v$.

Đồ thị đảm bảo là DAG (không có chu trình). Không có cạnh trùng lặp.

Dữ liệu ra

In ra một số nguyên duy nhất - tổng giá trị cảm xúc lớn nhất của một chuỗi ký ức có ý nghĩa (đường đi palindrome).

Ràng buộc

• $1\le N\le 1500$
• $0\le M\le 5000$
• $1\le w_i\le {10}^9$
• $c_i$ là chữ cái thường Latin ('a' - 'z')
• Đồ thị là DAG, không có cạnh trùng lặp
• Đường đi có thể có độ dài $1$ (chỉ một đỉnh duy nhất)

Ví dụ