Problem E: アニペロ

猛暑が続いた、長かったようで短かったような夏がもうすぐ終わろうとしていた。 そんな8月下旬のある日、とある2D好きな人物とその先輩のslipは、アニペロサマーライブ、通称アニペロと呼ばれるイベントに参加していた。 アニペロとは、さまざまなアニメソングアーティストたちが集結する、日本国内最大のアニメソングライブイベントである。 今年のアニペロは、公式で公表されていたアーティストの他に、シークレットで超豪華歌手も出演し、大盛況の内に幕を閉じた。 アニペロには初参戦だった2D好きな彼は、ライブ後の余韻にひたりつつも、ひとつの疑問を抱えていた。 「アニペロに出演するアーティストはどのように決めているのだろうか？」 彼は、数あるアーティストの中から、出演アーティストの選出をするのに、次のような方法があるのではないかと、選出法を考えてみた。

まず、アニペロのアーティストには、シークレットアーティストとスタンダードアーティストの2種類の分類があるものとする。 シークレットアーティストとは、ライブに出演することを事前公表せず、ライブ本番になって突然現れるアーティストのことを指す。 スタンダードアーティストとは、ライブに出演することを事前に公表してよいアーティストのことを指す。

全てのアーティストは、次のステータスを持つ。

• アーティスト名：文字列
• アーティストを雇うための金額（以下、雇用金と呼ぶ）：自然数
• このアーティストが出演することで、お客をどれほど満足させられるか（以下、満足度と呼ぶ）：自然数

今回、ライブに出演するアーティストを選ぶために、シークレットアーティスト候補N人、スタンダードアーティスト候補M人が、すでに用意されているものとする。さらに、ライブの主催者は、アーティストを雇用するために使用できる資金LIMITを持っているものとする。

主催者は、次の条件を満たすように、アーティストを選出しなければならない。

• N人のシークレットアーティスト枠から、1人以上、2人以下を選出する(1人or2人なのは、シークレットがいなかったり多かったりすることを避けるためである)
• M人のスタンダードアーティスト枠から、X人以上のアーティストを選出する
• アーティストを全て選出し終えたとき、雇用金の合計を、LIMIT以下にする
• 選出したアーティスト全員で得られる満足度の合計を最大化する

さて、ここまで選出法を考えた2D好きな彼は、この方法でプログラムを書いてみようと思った。しかし、彼は選出法を考えるのに気力を使ってしまい、プログラムを書く気力がなくなってしまったようなので、彼の代わりにプログラムを書いてあげてほしい。

あなたの仕事は、上記の選出法に従い、アーティストを選出したときのお客の最大満足度を出力するプログラムを作成することである。

Input

入力は、複数のデータセットからなる。データセットの総数は20以下である。 各データセットは、次の形をしている。

LIMIT N M X
SEC_NAME1 SEC_E1 SEC_S1
...
SEC_NAMEi SEC_Ei SEC_Si
...
SEC_NAMEN SEC_EN SEC_SN
NAME1 E1 S1
...
NAMEi Ei Si
...
NAMEM EM SM

整数LIMIT(4 ≤ LIMIT ≤ 1000)、N(2 ≤ N ≤ 100)、M(2 ≤ M ≤ 100)、X(2 ≤ X ≤ M)は、 それぞれアーティストを雇用するのに使用できる資金、シークレットアーティスト候補の数、スタンダードアーティスト候補の数、スタンダードアーティストから選出しなければならない最低人数を表す。 SEC_NAME_i、NAME_i、はそれぞれシークレットアーティスト候補、スタンダードアーティスト候補の名前を指す30文字以下の文字列である。 文字列には、アルファベット('A'-'Z', 'a'-'z')のみが使用される。 同じアーティスト名が2回以上出現することはない。 整数SEC_E_i、E_i (1 ≤ SEC_E_i, E_i ≤ 10)、SEC_S_i、S_i (1 ≤ SEC_S_i, S_i ≤ 10) は、それぞれシークレットアーティスト候補の雇用金、スタンダードアーティスト候補の雇用金、シークレットアーティスト候補が出演したときに得られる満足度、スタンダードアーティスト候補が出演したときに得られる満足度を表す。

入力の終了は、0が4つの行で示される。このデータについては処理する必要はない。

Output

選出法を適用してアーティストを選出したとき、お客の満足度の最大値を出力せよ。 アーティストの選出の仕方は、必ずあると仮定してよい。

Sample Input

100 2 2 2
A 5 6
B 7 8
C 1 2
D 3 4
27 2 3 3
A 8 10
B 8 10
C 6 7
D 5 4
E 8 9
27 2 3 2
A 8 10
B 8 10
C 6 7
D 5 4
E 8 9
44 3 6 5
YamatoNoHito 9 10
ZettoNoHito 9 10
TMR 10 10
SkillNoGroup 8 10
NanaSama 6 9
FRPSD 6 8
Magi3rdDeshi 5 7
Magi13thDeshi 2 2
MagicalItoh 4 6
0 0 0 0

Output for Sample Input

20
30
31
55

Note

Commentary

 

---