influencer

問題

インフルエンサーになりたい A さんは Twitter アカウントを作成しました。A さんは初めてのツイートとして長さ $N$ の文字列 $S$ を考えました。

A さんはツイートを投稿する前にインターネットで購入した情報商材を確認しました。すると Twitter にはハッシュタグという機能があり、それを使うことでツイートに拡散力を得られることが分かりました。

情報商材には $M$ 個のハッシュタグと、そのハッシュタグを用いることで得られる拡散力が記載されていました。具体的には $1 \leq i \leq M$ を満たす整数 $i$ について、文字列 $T_i$ をハッシュタグにすると $p_i$ の拡散力を得られることが書かれていました。

A さんが文字列 $S$ をいくつかの連続部分文字列に分解し、それらの連続部分文字列の中で情報商材に記載されているものをハッシュタグにした場合に得られるツイートの拡散力の総和として考えられる最大値を求めてください。

ただし同一のハッシュタグを複数回使用しても $2$ 回目以降の使用で新たに拡散力を得ることはできないものとします。

制約

• $1 \leq N \leq 5000$
• $1 \leq M \leq 10$
• $1 \leq |T_i| \leq N \hspace{0.5em} (\mathrm{for} \hspace{0.3em} 1 \leq i \leq M)$
• $1 \leq p_i \leq 10^8 \hspace{0.5em} (\mathrm{for} \hspace{0.3em} 1 \leq i \leq M)$
• $T_i \ne T_j \hspace{0.5em} (\mathrm{for} \hspace{0.3em} i \ne j)$

• $N, M$ は整数
• $S$ は英小文字からなる長さ $N$ の文字列
• $T_i$ は英小文字からなる文字列 $\hspace{0.25em} (\mathrm{for} \hspace{0.3em} 1 \leq i \leq M)$
• $p_i$ は整数 $\hspace{0.25em} (\mathrm{for} \hspace{0.3em} 1 \leq i \leq M)$

入力

入力は標準入力から以下の形式で与えられます。

出力

標準出力に答えを出力してください。

入出力例

例 1

10
appleapple
2
apple 5
applea 6

6

$\mathtt{appleapple}$ を $\mathtt{\textcolor{blue}{\#apple}\ apple}$ または $\mathtt{apple\ \textcolor{blue}{\#apple}}$ または $\mathtt{\textcolor{blue}{\#apple}\ \textcolor{blue}{\#apple}}$ とすることでハッシュタグ $\mathtt{\#apple}$ を使用できます。

また、$\mathtt{\textcolor{blue}{\#applea}\ pple}$ とすることでハッシュタグ $\mathtt{\#applea}$ を使用できます。

文字列 $\mathtt{appleapple}$ の長さは $10$ であるため、この文字列をどのように分割しても $\mathtt{\#apple}$ と $\mathtt{\#applea}$ を同時に使用することはできません。したがって、$\mathtt{\#applea}$ のみを使用したときのツイートの拡散力 $6$ が求める最大値となります。

例 2

7
abcdeab
3
aaa 10
bb 20
c 30

30

$\mathtt{ab\ \textcolor{blue}{\#c}\ deab}$ とすると拡散力 $30$ を得られ、これが最大です。

例 3

5
aaaaa
4
a 1
aa 10
aaa 100
aaaa 1000

1001

$\mathtt{\textcolor{blue}{\#a}\ \textcolor{blue}{\#aaaa}}$ または $\mathtt{\textcolor{blue}{\#aaaa}\ \textcolor{blue}{\#a}}$ とすると拡散力 $1001$ を得られ、これが最大です。