AT_tenka1_2016_final_c たんごたくさん

[problemUrl]: https://atcoder.jp/contests/tenka1-2016-final/tasks/tenka1_2016_final_c 文字列 $ S $ と、要素数 $ M $ の単語の集合 $ P=\{P_1,\ P_2,\ …,\ P_M\} $ が与えられます。単語 $ P_i $ は、整数の重み $ W_i $ を持っています。 文字列 $ S $ から、$ P $ に含まれる単語を重なり合わないように取り出すことを考えます。単語の重みの総和が最大値をとるように取り出すとき、その最大値はいくつでしょうか？ なお、同じ単語を複数回取り出した場合、それらの単語は別々に数えることとします。

入力は以下の形式で標準入力から与えられる。 > $ S $ $ M $ $ P_1 $ : $ P_M $ $ W_1 $ : $ W_M $

単語の重みの総和の最大値を $ 1 $ 行に出力せよ。

### 制約 - $ 1\ \leq\ |S|\ \leq\ 200000 $ - $ 1\ \leq\ M\ \leq\ 5000 $ - $ 1\ \leq\ |P_i|\ \leq\ 200 $ - $ 1\ \leq\ W_i\ \leq\ 10000 $ - $ S $, $ P_i $ は英小文字からなる文字列である