시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 (추가 시간 없음) 512 MB0000.000%

문제

バイオベンチャーの ICPC (International Cucumber Planting Company) は燃料用枝豆の育成に取り組んでいる.彼らがベンチャーキャピタルに提出した事業計画によると,ICPC 社の技術で特別に品種改良した枝豆を特定の薬品で化学処理することで燃料用エタノールを得ることが可能らしい(もともとはきゅうりの改良に取り組んでいたが,こちらはうまくいかなかった).

その枝豆がまもなく収穫の時期を迎えようとしている.この枝豆の鞘には M 粒の豆が一列に並んでおり,粒ごとに異なる特性を持っているので本来はそれぞれ異なる化学処理が必要となる.

化学処理に用いられる薬品は全部で N 種類ある.それぞれの豆粒には 2 個の特性があり,そのどちらかが満たされていれば燃料にすることが可能である.特性には「ある薬品を用いる」ものと「ある薬品を用いない」ものの 2 種類がある.

  • 特性 P(x): 種類 x の薬品が有効である(種類 x の薬品を用いると処理できる)
  • 特性 Q(x): 種類 x の薬品によって阻害される,その豆粒に有効な自己分解酵素を持っている(種類 x の薬品を用いなければ処理できる)

たとえば,ある豆粒が P(x) と Q(y) の特性を持っているとすると,この豆粒は種類 x の薬品を用いることで処理できるほか,種類 x の薬品が用いられていない場合でも種類 y の薬品さえ用いられていなければ,処理することができる.また,ある豆粒が持つ 2 個の特性は同じタイプである場合もあり,たとえば,P(x) と P(y) の特性を持っているとすると,この豆粒は種類 x または y の薬品を用いると処理することができる.

長きにわたる研究開発で資金が底をつきかけている ICPC 社には,枝豆を 1 粒ずつ取り出してそれぞれに適切な処理を行うような設備に投資する余力は残されていなかった.代替案として,0 種類以上の薬品を混合して作った処理液を用いて,枝豆の両端から 0 個以上の連続する豆粒を捨て,中央の残った豆粒をすべてまとめて処理する工程を採用することにした.このとき,薬品や枝豆は特性に表現されている以外の相互作用を起こさないことがわかっている.しかし,処理できていない豆粒が残っていると後工程に支障が出るのでこれは許されない.

もちろん,設備の収率を上げるには捨てる豆粒ができるだけ少ないほうがよい.ICPC 社のソフトウェアエンジニアであるあなたの仕事は,処理液に用いる薬品の種類を適切に選ぶことでできるだけ多くの豆粒を使えるように計画するプログラムを書くことである.

たとえば,入出力例の 1 つ目のデータセットでは,種類 1 と 2 の薬品を混合した処理液を用いることで,1 番目から 3 番目までの豆粒を処理できる.しかし,種類 1 と 2 の薬品をそれぞれ使う・使わない全 4 通りの処理液のいずれでもどれか 1 つの豆粒は処理できない.したがってこのデータセットの答えは 3 である.2 つ目のデータセットにあるように,1 つの豆粒が同じ特性を重複して持つ場合もあるので注意せよ.この場合も 2 つのうちのいずれかの条件を満たしていれば処理できる.3 つ目のデータセットでは,いずれの薬品も用いない処理液を用いることですべての豆粒を処理できる.

입력

入力は 50 個以下のデータセットからなる. 各データセットは次の形式で表される.

N M
a1 b1
...
aM bM

最初の行は薬品の種類数 N (1 ≤ N ≤ 2000) と枝豆に含まれる粒数 M (1 ≤ M ≤ 2000) がこの順で与えられる.続く M 行に豆粒に関する情報が 1 行ずつ与えられる. 1 + i 行目には端から数えて i 番目の豆粒の特性を表す 2 つの整数 ai と bi が与えられる.この整数を x とすると -N ≤ x ≤ N, x ≠ 0 を満たし,x が正のときは i 番目の豆粒は種類 x の薬品で処理できること,すなわち特性 P(x) を持っていること,x が負のときは i 番目の豆粒は種類 |x| の薬品を用いなければ処理できること,すなわち特性 Q(|x|) を持っていることをそれぞれ意味する.

入力の終わりは 2 つの 0 からなる行で表される.

출력

各データセットに対し,処理に使用することができる最大の豆粒の数を 1 行に出力せよ.

예제 입력 1

2 4
1 2
1 -2
-1 2
-1 -2
1 2
1 1
-1 -1
10 5
-1 -2
-3 -4
-5 -6
-7 -8
-9 -10
3 3
1 -1
2 -2
3 -3
2 5
1 1
2 2
-1 -1
2 2
1 1
0 0

예제 출력 1

3
1
5
3
3