幼稚園生の千咲ちゃんは、遠足にお菓子をもっていくことにした。
お菓子は $N$ 個あって、$i$ 番目のお菓子は値段が $A_i$ 円で、美味しさが $B_i$ である。
千咲ちゃんには友達が $M$ 人いて、$j$ 番目の友達は、値段が $C_j$ 円以上のお菓子を $D_j$ 個以上千咲ちゃんがもっていると泣きわめく。
友達が泣きわめいてしまうと千咲ちゃんはかなしいので、そうならないようにお菓子をもっていきたい。
お菓子の美味しさの合計は最大でいくつになるか求めて、千咲ちゃんを助けなさい。
1 行目には、お菓子の個数 $N$ と、友達の人数 $M$ が空白区切りで与えられる。
続く $N$ 行のうち $i$ 行目には、$A_i, B_i$ が空白区切りで与えられる。
続く $M$ 行のうち $j$ 行目には、$C_j, D_j$ が空白区切りで与えられる。
どの友達も泣かないように持っていくお菓子を選んだ時、その美味しさの合計としてありうる最大値を出力せよ。
3 1 10 1 20 2 30 3 20 2
4
$1, 3$ 番目のお菓子を持っていくと、友達を泣かせない範囲で、持ってくるお菓子の美味しさの合計を最大化することができます。
$2, 3$ 番目のお菓子両方を持っていくと、「値段が $20$ 円以上のお菓子を $2$ 個以上持ってくる」ことになるので、友達が泣きます。
5 3 10 1 20 4 30 5 40 2 50 3 20 3 30 4 40 2
10
$1, 2, 3$ 番目のお菓子を持っていくことによって、どの友達も泣かせない条件のもとで、持ってくるお菓子の美味しさの合計を最大化することができます。