A string is said to contain a value that is known as its beauty.

You are given \(M\) pairings where the \(i^{th}\) pairing is \(\{(a_i, b_i):k_i\}\). Here, \(a_i\) and \(b_i\) are lowercase English letters and \(k_i\) is a positive integer.

There exists a string \(S\) of length \(L\). For the \(i^{th}\) pairing, let the number of indices \(j ∈ [1, L - 1]\) such that \(S_j = a_i\) and \(S_{j+1} = b_i\) be \(count_i\). The beauty of \(S\) is the sum of \(count_i * k_i\) for each \(i ∈ [1, M]\).

You are given a string \(A\) of length \(N\) consisting of lowercase English letters. A string can be formed from a subsequence of a string by concatenating the characters of the subsequence in order of occurrence. You are required to find the maximum beauty that can be obtained by selecting any strings that can be formed by a subsequence of \(A\).

Input format

• The first line contains a single integer \(N\) that denotes the length of string \(A\).
• The second line contains string \(A\).
• The third line contains a single integer \(M\) which denotes the number of pairings.
• The next \(M\) lines represent the pairings. Each of these lines contain three space-separated values. The first two are the lowercase English letters \(a_i\) and \(b_i\). The third value is the integer \(k_i\).

Output format

Print a single line containing the maximum beauty that can be obtained from a string formed by a subsequence of \(A\).

Constraints

\(S_j,\ a_i,\ b_i\) are lowercase English letters.