あなたは,絵の展覧会を開催しようとしている.展覧会では,いくつかの絵を額縁に入れ,左から右に一列に並べて展示する.
展覧会で展示する候補となる絵が$N$ 枚あり,1 から$N$ までの番号が付けられている.絵$i$ ($1 \leq i \leq N$) の大きさは$S_i$,価値は$V_i$ である.
また,これらの絵を入れるための額縁が$M$ 枚あり,1 から$M$ までの番号が付けられている.額縁$j$ ($1 \leq j \leq M$) の大きさは$C_j$ である.額縁$j$ には,大きさが$C_j$ 以下の絵のみを入れることができる.1 枚の額縁には高々1 枚の絵しか入れることができない.
展示する絵はすべて何らかの額縁に入っていなければならない.見栄えを良くするため,展示する絵は以下の条件を満たさなければならない:
あなたは,できるだけ多くの絵を展示したい.
展示候補の絵の枚数,額縁の枚数,及びそれらの大きさや価値が与えられたとき,展示する絵の枚数の最大値を求めるプログラムを作成せよ.
入力は以下の形式で標準入力から与えられる.
$N$ $M$ $S_1$ $V_1$ : $S_N$ $V_N$ $C_1$ : $C_M$
標準出力に,展覧会に展示する絵の枚数の最大値を1 行で出力せよ.
3 4 10 20 5 1 3 5 4 6 10 4
2
この入出力例では,左から順に(絵2, 額縁2),(絵1, 額縁3) と並べることで,2 枚の絵を展示することができる.3 枚以上の絵を展示することはできないので,2 を出力する.ここで,(絵$i$, 額縁$j$) は,額縁$j$に入った絵$i$ を表す.
3 2 1 2 1 2 1 2 1 1
2
4 2 28 1 8 8 6 10 16 9 4 3
0
8 8 508917604 35617051 501958939 840246141 485338402 32896484 957730250 357542366 904165504 137209882 684085683 775621730 552953629 20004459 125090903 607302990 433255278 979756183 28423637 856448848 276518245 314201319 666094038 149542543
3
情報オリンピック日本委員会作 『第18 回日本情報オリンピック(JOI 2018/2019) 本選』