0359 - 総和占い (Fortune Telling 2)

問題

　K 理事長は占いが好きで，いつも様々な占いをしている．今日はカードを使って今年の IOI での日本選手団の出来を占うことにした．
　今回使用するカードにはその両面に整数が書かれている．両面に書かれている整数は同じとは限らず，片方の面の整数が見えるようにカードを置いたとき，もう一方の面の整数は見えなくなる．
　占いの方法は次のようなものである．

• まず N 枚のカードを用意し，机に置く．カードには 1 から N までの番号がついており，カード i に書かれている整数は A_i と B_i である．カード i は A_i が書かれている面を上にして置かれる．
• j = 1, ..., K について，「それぞれのカードに対し，見えている整数が T_j 以下であればそのカードの表裏をひっくり返す」という操作を行う．
• K 回の操作が終わった後，見えている整数をすべて足した値の大きさによって占いの結果が出る．

　K 理事長は途中でひっくり返すカードを選ぶのがあまりに大変であることに気付いたので，カードを実際に使って占うのはやめて，操作が終わった後に見えている整数の総和だけを求めることにした．

課題

　カードに書かれている整数および操作の指示が与えられたとき，操作後に見えている整数の総和を求めるプログラムを作成せよ．

入力

　標準入力から以下の入力を読み込め．

• 1 行目には，2 つの整数 N, K が空白を区切りとして書かれており，カードの枚数が N，操作の回数が K であることを表す．
• 続く N 行のうちの i 行目 (1 ≦ i ≦ N) には，2 つの整数 A_i, B_i が書かれている．これは，カード i のそれぞれの面に書かれている整数が A_i と B_i であることを表す．
• 続く K 行のうちの j 行目 (1 ≦ j ≦ K) には，整数 T_j が書かれている．これは，j 回目の操作では見えている整数が T_j 以下であるようなカードをひっくり返すことを表す．

出力

　標準出力に，K 回の操作後に見えている整数の総和を 1 行で出力せよ．

制限

　すべての入力データは以下の条件を満たす.

• 1 ≦ N ≦ 200 000．
• 1 ≦ K ≦ 200 000．
• 1 ≦ A_i ≦ 1 000 000 000 (1 ≦ i ≦ N)．
• 1 ≦ B_i ≦ 1 000 000 000 (1 ≦ i ≦ N)．
• 1 ≦ T_j ≦ 1 000 000 000 (1 ≦ j ≦ K)．

小課題

小課題 1 [4 点]

　以下の条件を満たす．

• N ≦ 1 000．
• K ≦ 1 000．

小課題 2 [31 点]

　以下の条件を満たす．

• N ≦ 40 000．
• K ≦ 40 000．

小課題 3 [65 点]

　追加の制限はない．

入出力例

入力例 1

5 3
4 6
9 1
8 8
4 2
3 7
8
2
9

出力例 1

18

　はじめ，見えている 5 つの整数は 4, 9, 8, 4, 3 である．それぞれの操作を順に行っていくと，次のようになる．

• 見えている整数が 8 以下であるようなカードをすべてひっくり返すと，見えている整数は 6, 9, 8, 2, 7 となる．
• 見えている整数が 2 以下であるようなカードをすべてひっくり返すと，見えている整数は 6, 9, 8, 4, 7 となる．
• 見えている整数が 9 以下であるようなカードをすべてひっくり返すと，見えている整数は 4, 1, 8, 2, 3 となる．

　したがって，すべての操作を終えた後に見えている整数の合計は 4 + 1 + 8 + 2 + 3 = 18 である．