AT_joi2019ho_b 展覧会 (Exhibition)

[problemUrl]: https://atcoder.jp/contests/joi2019ho/tasks/joi2019ho_b あなたは，絵の展覧会を開催しようとしている．展覧会では，いくつかの絵を額縁に入れ，左から右に一列に並べて展示する． 展覧会で展示する候補となる絵が $ N $ 枚あり，$ 1 $ から $ N $ までの番号が付けられている．絵 $ i $ ($ 1\ \leqq\ i\ \leqq\ N $) の大きさは $ S_i $，価値は $ V_i $ である． また，これらの絵を入れるための額縁が $ M $ 枚あり，$ 1 $ から $ M $ までの番号が付けられている．額縁 $ j $ ($ 1\ \leqq\ j\ \leqq\ M $) の大きさは $ C_j $ である．額縁 $ j $ には，大きさが $ C_j $ 以下の絵のみを入れることができる．$ 1 $ 枚の額縁には高々 $ 1 $ 枚の絵しか入れることができない． 展示する絵はすべて何らかの額縁に入っていなければならない．見栄えを良くするため，展示する絵は以下の条件を満たさなければならない： - 左右に隣り合うどの $ 2 $ 枚の絵についても，右側の絵が入っている額縁の大きさは左側の絵が入っている額縁の大きさ以上である． - 左右に隣り合うどの $ 2 $ 枚の絵についても，右側の絵の価値は左側の絵の価値以上である． あなたは，できるだけ多くの絵を展示したい． 展示候補の絵の枚数，額縁の枚数，及びそれらの大きさや価値が与えられたとき，展示する絵の枚数の最大値を求めるプログラムを作成せよ． - - - - - -

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ S_1 $ $ V_1 $ $ \vdots $ $ S_N $ $ V_N $ $ C_1 $ $ \vdots $ $ C_M $

標準出力に，展覧会に展示する絵の枚数の最大値を $ 1 $ 行で出力せよ． - - - - - -

### 制約 - $ 1\ \leqq\ N\ \leqq\ 100\,000 $． - $ 1\ \leqq\ M\ \leqq\ 100\,000 $． - $ 1\ \leqq\ S_i\ \leqq\ 1\,000\,000\,000 $ ($ 1\ \leqq\ i\ \leqq\ N $)． - $ 1\ \leqq\ V_i\ \leqq\ 1\,000\,000\,000 $ ($ 1\ \leqq\ i\ \leqq\ N $)． - $ 1\ \leqq\ C_j\ \leqq\ 1\,000\,000\,000 $ ($ 1\ \leqq\ j\ \leqq\ M $)． ### 小課題 1. ($ 10 $ 点) $ N\ \leqq\ 10 $，$ M\ \leqq\ 10 $． 2. ($ 40 $ 点) $ N\ \leqq\ 1\,000 $，$ M\ \leqq\ 1\,000 $． 3. ($ 50 $ 点) 追加の制約はない． - - - - - - ### Sample Explanation 1 この入出力例では，左から順に (絵 $ 2 $, 額縁 $ 2 $)，(絵 $ 1 $, 額縁 $ 3 $) と並べることで，$ 2 $ 枚の絵を展示することができる．$ 3 $ 枚以上の絵を展示することはできないので，$ 2 $ を出力する．ここで，(絵 $ i $, 額縁 $ j $) は，額縁 $ j $ に入った絵 $ i $ を表す． - - - - - - ### Sample Explanation 2 \- - - - - - ### Sample Explanation 3 \- - - - - -