あなたはネットカフェを経営しています。今日あなたは、顧客に指摘され続けている問題を解決しようと取り組んでいます。その問題とは、店舗の本棚の単行本が巻数順に並んでおらず、目的の単行本を探しだすのが面倒だという苦情です。
あなたの店舗で一番巻数の多い単行本は「名探偵 赤ベコ」(通称「赤ベコ」)です。あまりに長編なので、特別な本棚を「赤ベコ」のために用意しました。
単行本の各巻の重さと厚さは様々で、本棚の各段の幅と、各段に並べることができる本の重さの上限も様々です。あなたは、次の条件を満足するように本棚に本を並べることにしました。
これらの条件を満たしたとき,この本棚に最大で何巻まで「赤ベコ」を並べることができるかを求めるプログラムを作成してください。
入力は以下の形式で与えられる。
M N w1 t1 w2 t2 : wM tM c1 b1 c2 b2 : cN bN
最初の1行に「赤ベコ」の巻数 M (1 ≤ M ≤ 200000) と本棚の段数 N (1 ≤ N ≤ 15) が与えられる。続く M 行に、「赤ベコ」の単行本 i 巻目の重さ wi (1 ≤ wi ≤ 100) と厚さ ti (1 ≤ ti ≤ 100) を表す整数が与えられる。続く N 行に、本棚の i 段目の重さの上限 ci (1 ≤ ci ≤ 108)と幅 bi (1 ≤ bi ≤ 108) を表す整数が与えられる。
本棚に並べることができる最大の「赤ベコ」巻数を1行に出力する。
3 4 2 2 3 3 4 4 3 3 4 4 1 1 2 2
3
2 2 1 2 2 1 2 1 2 1
0
3 2 1 2 2 2 2 1 3 3 2 2
2
3 2 1 2 2 1 2 2 2 2 3 3
3