Problem G : Everything Starts With Your Vote

ヒューリスティクスという言葉がある。確実にうまくいくという保証はないけれども大抵の場合はうまくいく、比較的単純なアプローチのことだ。単純にして強力であるがゆえに、この世の中は多くのヒューリスティクスで満ち溢れている。

ヒューリスティクスの一例として、こんなものが挙げられる。アニメ番組において、あるキャラクターの人気度は、そのアニメ本編中における登場時間の総和に比例する。確かにこれは多くの場合に成り立っているようだ。しかし、どうやら僕は少数派に属するらしい。影の薄いキャラ、背景にちらりと映るモブキャラなんかに限って可愛く見えたりするのだ。

自分の好きなキャラのことを、他人がどう思っていようがいいじゃないか。とは言ってられない事情が、残念ながらある。関連商品、フィギュアやキャラクターソングCDなどは、人気のあるキャラのものから優先的に発売される傾向にあるのだ。商業的には当然の選択だとはいえ、不人気キャラのファンの肩身は狭い。

そこで重要となってくるのが、アニメ番組の制作会社によって行われる人気投票である。実際の人気がどうであれ、ここで多くの票を獲得すれば、関連商品への道が開かれるのだ。どんな手段を使っても票を集めねばなるまい。

厳正なる投票のために、ある関連商品を1つ購入するたびに1票の投票権が与えられる。この仕組を厳正と呼ぶべきかどうかは今大きく議論されているが、とにかく僕は L 票の投票権を得た。投票の対象となるキャラは全部で N 人いて、より多くの票を獲得した K 人のキャラ (同票の場合は名前の辞書順) の関連商品が企画されることになる。僕の好きなキャラは全部で M 人いて、その中からできるだけ多くのキャラを上位 K 人に入れたいと思っている。

僕はまず、それぞれのキャラがどれだけの票を獲得するかを予測した(難しいことではない。あるキャラクターの人気度は、その登場時間の総和に比例すると仮定しただけだ)。この予測が正しいとして、より多くの僕の好きなキャラの関連商品が発売されるようにするためには、僕はこの L 票を誰にどれだけ投じればいいだろうか。

Input

入力は複数のケースからなる。 各ケースは以下のフォーマットで与えられる。

N M K L
name0 x0
.
.
.
nameN-1 xN-1
fav0
.
.
.
favM-1

N、M、K、Lの意味は問題文に記されているとおりである。
name_i　はキャラクターの名前、x_i　はi 番目のキャラクターの票の総数を表す。
fav_i はあなたがひいきしているキャラクターの名前を表す。これらの名前は必ず異なり、また必ずキャラクターの名前の入力の中に含まれる。

入力の終わりはN = 0 かつ M = 0 かつ K = 0 かつ L = 0からなる行によって与えられる

また各値は以下の条件を満たす
1 ≤ N ≤ 100,000
1 ≤ M ≤ N
1 ≤ K ≤ N
1 ≤ L ≤ 100,000,000
0 ≤ x_i ≤ 100,000,000
name_iはアルファベットのみを含み、長さは10文字以下である。

テストケースの数は150を超えない。
また20,000 ≤ N となるケースの数は20を超えないことが保証されている。

ジャッジデータは大きいので、速い入力を使うことを推奨する。

Output

M 人のキャラの中から最大で何人を上位K 人に入れることが出来るかを1行で出力せよ。

Sample input

4 1 3 4
yskwcnt 16
akzakr 7
tsnukk 12
fnmyi 13
akzakr
4 1 3 5
akzakr 7
tsnukk 12
fnmyi 13
yskwcnt 16
akzakr
4 2 2 1
akzakr 4
tsnukk 6
yskwcnt 6
fnmyi 12
akzakr
fnmyi
5 2 3 28
knmmdk 6
skrkyk 14
tmemm 14
akmhmr 15
mksyk 25
knmmdk
skrkyk
5 2 3 11
tmemm 12
skrkyk 18
knmmdk 21
mksyk 23
akmhmr 42
skrkyk
tmemm
14 5 10 38
iormns 19
hbkgnh 23
yyitktk 31
rtkakzk 36
mmftm 43
ykhhgwr 65
hrkamm 66
ktrotns 67
mktkkc 68
mkhsi 69
azsmur 73
tknsj 73
amftm 81
chyksrg 88
mkhsi
hbkgnh
mktkkc
yyitktk
tknsj
14 5 10 38
mktkkc 24
rtkakzk 25
ykhhgwr 25
hrkamm 27
amftm 37
iormns 38
tknsj 38
yyitktk 39
hbkgnh 53
mmftm 53
chyksrg 63
ktrotns 63
azsmur 65
mkhsi 76
mkhsi
hbkgnh
mktkkc
yyitktk
tknsj
0 0 0 0

Sample output

0
1
1
2
1
4
5

The University of Aizu Programming Contest 2011 Summer
原案: Tomoya Sakai
問題文: Takashi Tayama