G - 主菜と副菜
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 種類の主菜と M 種類の副菜から料理を選んでコースを作ります。 主菜は 1 種類しか選ぶことができませんが、副菜は何種類でも選ぶことができます。 また、副菜は 1 つも選ばなくても構いません。 主菜・副菜ともにコースに入れられるのは 1 種類につき 1 つまでです。
- i 番目の主菜は値段が A_i で、お客さんの評価が B_i です。
- i 番目の副菜は値段が C_i で、お客さんの評価が D_i です。
コース全体の値段と評価は、主菜と副菜の合計で決まります。 コースの値段を L 以下にする時、コースの評価は最大でいくつになるか求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N M L A_1 B_1 : A_N B_N C_1 D_1 : C_M D_M
- 1 行目には、3 つの整数 N (1 ≦ N ≦ 10,000), M (1 ≦ M ≦ 1,000), L (1 ≦ L ≦ 10,000) が空白区切りで与えられる。
- 2 行目からの N 行には、主菜の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、i 番目の主菜の値段と評価を表す整数 A_i (1 ≦ A_i ≦ 10,000), B_i (1 ≦ B_i ≦ 10,000) が与えられる。
- N+2 行目からの M 行には、副菜の情報が与えられる。このうち i (1 ≦ i ≦ M) 行目には、i 番目の副菜の値段と評価を表す整数 C_i (1 ≦ C_i ≦ 10,000), D_i (1 ≦ D_i ≦ 10,000) が与えられる。
- 必ずコースを作れることが保証される。
出力
コースの評価の最大値を 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
2 2 10 2 3 3 6 3 5 5 5
出力例1
13
入力例2
3 3 10 1 1 2 3 3 5 4 8 5 10 6 12
出力例2
19
入力例3
3 3 10 1 1 11 11 11 11 11 11 11 11 11 11
出力例3
1