問題
インフルエンサーになりたい A さんは Twitter アカウントを作成しました。A さんは初めてのツイートとして長さ N の文字列 S を考えました。
A さんはツイートを投稿する前にインターネットで購入した情報商材を確認しました。すると Twitter にはハッシュタグという機能があり、それを使うことでツイートに拡散力を得られることが分かりました。
情報商材には M 個のハッシュタグと、そのハッシュタグを用いることで得られる拡散力が記載されていました。具体的には 1≤i≤M を満たす整数 i について、文字列 Ti をハッシュタグにすると pi の拡散力を得られることが書かれていました。
A さんが文字列 S をいくつかの連続部分文字列に分解し、それらの連続部分文字列の中で情報商材に記載されているものをハッシュタグにした場合に得られるツイートの拡散力の総和として考えられる最大値を求めてください。
ただし同一のハッシュタグを複数回使用しても 2 回目以降の使用で新たに拡散力を得ることはできないものとします。
制約
- 1≤N≤5000
- 1≤M≤10
- 1≤∣Ti∣≤N(for1≤i≤M)
- 1≤pi≤108(for1≤i≤M)
- Ti=Tj(fori=j)
- N,M は整数
- S は英小文字からなる長さ N の文字列
- Ti は英小文字からなる文字列 (for1≤i≤M)
- pi は整数 (for1≤i≤M)
入力
入力は標準入力から以下の形式で与えられます。
出力
標準出力に答えを出力してください。
入出力例
例 1
入力
10
appleapple
2
apple 5
applea 6
appleapple を #apple apple または apple #apple または #apple #apple とすることでハッシュタグ #apple を使用できます。
また、#applea pple とすることでハッシュタグ #applea を使用できます。
文字列 appleapple の長さは 10 であるため、この文字列をどのように分割しても #apple と #applea を同時に使用することはできません。したがって、#applea のみを使用したときのツイートの拡散力 6 が求める最大値となります。
例 2
入力
7
abcdeab
3
aaa 10
bb 20
c 30
ab #c deab とすると拡散力 30 を得られ、これが最大です。
例 3
入力
5
aaaaa
4
a 1
aa 10
aaa 100
aaaa 1000
#a #aaaa または #aaaa #a とすると拡散力 1001 を得られ、これが最大です。