Tên nhân vật

Cho xâu $s$ gồm các chữ cái Latin thường. Độ hay của một xâu được tính như sau: với mỗi cặp ký tự liền kề $x,y$ trong xâu (ký tự $x$ đứng ngay trước ký tự $y$), cộng vào kết quả giá trị thưởng $c(x,y)$.

Bảng thưởng được cho bởi $n$ bộ ba $(x,y,c)$ nghĩa là $c(x,y)=c$. Mọi cặp không được liệt kê có giá trị thưởng bằng $0$.

Bạn được phép thay đổi không quá $k$ ký tự của $s$: mỗi ký tự được chọn có thể đổi thành một chữ cái Latin thường bất kỳ, độ dài xâu giữ nguyên. Hãy tìm độ hay lớn nhất có thể đạt được sau khi thay đổi.

Dữ liệu vào

• Dòng đầu chứa xâu $s$ và số nguyên $k$, cách nhau bởi dấu cách.
• Dòng thứ hai chứa số nguyên $n$ là số cặp ký tự có giá trị thưởng.
• $n$ dòng tiếp theo, mỗi dòng chứa hai chữ cái Latin thường $x$, $y$ và số nguyên $c$, mô tả $c(x,y)=c$.

Dữ liệu ra

Một số nguyên duy nhất là độ hay lớn nhất có thể đạt được.

Ràng buộc

• $1\le |s|\le 100$, xâu $s$ chỉ gồm chữ cái Latin thường
• $0\le k\le 100$
• $0\le n\le 676$
• $-1000\le c\le 1000$
• Các cặp $(x,y)$ trong dữ liệu vào đôi một khác nhau

Ví dụ