Chisaki and Picnic

Time Limit : 2 sec, Memory Limit : 262144 KB

O: 千咲ちゃんと遠足 (Chisaki and Picnic)

幼稚園生の千咲ちゃんは、遠足にお菓子をもっていくことにした。

お菓子は $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$ が空白区切りで与えられる。

出力

どの友達も泣かないように持っていくお菓子を選んだ時、その美味しさの合計としてありうる最大値を出力せよ。

制約

  • $N, M$ は $1$ 以上 $100 \ 000$ 以下の整数
  • $A_1, A_2, A_3, \dots, A_N$ は $1$ 以上 $1 \ 000 \ 000 \ 000$ 以下の整数
  • $B_1, B_2, B_3, \dots, B_N$ は $1$ 以上 $1 \ 000 \ 000 \ 000$ 以下の整数
  • $A_1 \leq A_2 \leq A_3 \leq \cdots \leq A_N$ を満たす
  • $C_1, C_2, C_3, \dots, C_M$ は $1$ 以上 $1 \ 000 \ 000 \ 000$ 以下の整数
  • $D_1, D_2, D_3, \dots, D_M$ は $1$ 以上 $1 \ 000 \ 000 \ 000$ 以下の整数
  • $C_1 \leq C_2 \leq C_3 \leq \cdots \leq C_M$ を満たす

入力例1

3 1
10 1
20 2
30 3
20 2

出力例1

4

$1, 3$ 番目のお菓子を持っていくと、友達を泣かせない範囲で、持ってくるお菓子の美味しさの合計を最大化することができます。

$2, 3$ 番目のお菓子両方を持っていくと、「値段が $20$ 円以上のお菓子を $2$ 個以上持ってくる」ことになるので、友達が泣きます。

入力例2

5 3
10 1
20 4
30 5
40 2
50 3
20 3
30 4
40 2

出力例2

10

$1, 2, 3$ 番目のお菓子を持っていくことによって、どの友達も泣かせない条件のもとで、持ってくるお菓子の美味しさの合計を最大化することができます。