Net Cafe

Time Limit : 1 sec, Memory Limit : 65536 KB

ネットカフェ

あなたはネットカフェを経営しています。今日あなたは、顧客に指摘され続けている問題を解決しようと取り組んでいます。その問題とは、店舗の本棚の単行本が巻数順に並んでおらず、目的の単行本を探しだすのが面倒だという苦情です。

あなたの店舗で一番巻数の多い単行本は「名探偵 赤ベコ」(通称「赤ベコ」)です。あまりに長編なので、特別な本棚を「赤ベコ」のために用意しました。

単行本の各巻の重さと厚さは様々で、本棚の各段の幅と、各段に並べることができる本の重さの上限も様々です。あなたは、次の条件を満足するように本棚に本を並べることにしました。

  • 1 巻からある巻までの「赤ベコ」が本棚に並んでいる。
  • それぞれの段には、巻数順に(途中で抜けている巻がないように)本が並ぶ。
  • 各段に並べる本の重さの合計が、その段で定められた重さの上限を超えない。
  • 各段に並べる本の厚さの合計が、その段の幅を超えない。

これらの条件を満たしたとき,この本棚に最大で何巻まで「赤ベコ」を並べることができるかを求めるプログラムを作成してください。

入力

入力は以下の形式で与えられる。

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行に出力する。

入出力例

入力例1

3 4
2 2
3 3
4 4
3 3
4 4
1 1
2 2

出力例1

3

入力例2

2 2
1 2
2 1
2 1
2 1

出力例2

0

入力例3

3 2
1 2
2 2
2 1
3 3
2 2

出力例3

2

入力例4

3 2
1 2
2 1
2 2
2 2
3 3

出力例4

3

Source: PC Koshien 2014 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2014-11-8
http://web-ext.u-aizu.ac.jp/pc-concours/