リアルイベント問題セットのアイコン
文字列収集 (paizaランク S 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

Img 04 03 下記の問題をプログラミングしてみよう!

あなたは文字列の愛好家で、文字列を収集することにとても熱心です。

文字列は市場で高値で取引されています。今、市場には N 個の文字列が出まわっており、文字列 S_i (1 ≦ i ≦ N) の価格は P_i です。 あなたは数ある文字列の中でも、とくに先頭がある特定の文字列で始まる文字列に興味があり、そのような文字列をすべて買い占めたいです。例え、同じ文字列が複数売っていたとしてもそのすべてを買います。

そこで、市場に出回っている N 個の文字列 S_i とそれぞれの価格 P_i (i ≦ i ≦ N)、また、M 個のクエリ文字列 Q_i (1 ≦ i ≦ M) が与えられるので、それぞれのクエリ Q_i に対し、市場に出回っている文字列の中で先頭が Q_i で始まる文字列すべてを買い占めるのに必要な金額を出力するプログラムを作成してください。

入力される値

入力は以下のフォーマットで与えられます。

N M
S_1 P_1
S_2 P_2
...
S_N P_N
Q_1
Q_2
...
Q_M

ただし、文字列 S_i, Q_j (1 ≦ i ≦ N, 1 ≦ j ≦ M) は英小文字のみから構成されます。P_i は整数です。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

それぞれのクエリに対し、必要な金額を一行に出力してください。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ N ≦ 10000
・1 ≦ M ≦ 10000
・1 ≦ S_i の長さ ≦ 100 (1 ≦ i ≦ N)
・1 ≦ P_i ≦ 10000 (1 ≦ i ≦ N)
・1 ≦ Q_i の長さ ≦ 100 (1 ≦ i ≦ M)

入力例1

6 5
bcac 3
abcd 14
abccjg 92
bcaddgie 2
abcd 6
cb 200
b
a
abcd
gagioheo
cb

出力例1

5
112
20
0
200

入力例2

5 3
paiza 16
pizza 1
paizaio 4
paizapoh 2
pizzaio 8
paiza
pizza
p

出力例2

22
9
31

問題一覧へ戻る

ページの先頭へ戻る