acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem E

改竄された史料

太古の昔, International Collegiate Puzzle Contest (ICPC) というパズル大会が毎年開催されていた. 各大会は午前・午後の 2 つのラウンドで構成されていた. どちらのラウンドでも,参加者はまず自作のパズル 1 つを他の全参加者に提示し,その後に自分自身以外の全参加者が提示したパズルをできるだけ多く解こうとした.

参加者の順位は以下の規則に従って決めていた.

  • 午後のラウンドで解いたパズルの数がより多い参加者がより上位となる.
  • 午後のラウンドで同数のパズルを解いた参加者のなかでは,午前のラウンドで解いたパズルの数がより多い方が上位となる.
  • 両ラウンドで解いたパズルの数が完全に一致する参加者同士の順位はくじびきで決める.

先日,ある年の ICPC の順位表とされる文書が発見された. 他の同様の資料から,この文書は各ラウンドで解いたパズルの数を上位の参加者から順に書き並べたものと考えられる. ところが学者たちは文書は何者かによって改竄されていて,いくつかの数が書き換えられているのではないかという疑いを持っている. もともとの順位表に上述の規則と矛盾がなかったと仮定したとき,少なくともいくつの数が書き換えられているのかを求めてほしい. なお,文書中の解いたパズルの数以外の部分への改竄はなく,参加者の追加や削除もありえない.

Input

入力は複数のデータセットからなる. 各データセットは次の形式で表される.

n
x1 y1
 ⋮
xn yn

n は参加者数を表す 2 以上 6000 以下の整数である.

xiyi は,それぞれ順位が i 位の参加者が午前と午後に解いたパズルの数として現在文書に記載されている値を表す. xiyi はそれぞれ 0 以上 n 未満の整数である. これらの値のいくつかは,本来の値から改竄された結果である可能性がある.

入力の終わりは,1 つのゼロからなる行で表される. 入力に含まれるデータセットは 100 個以下である. また,全てのデータセットにおける n の合計は 105 を超えない.

Output

各データセットについて,文書に記された 2n 個の数値のうち,もとの順位表から書き換えられたものの個数としてありうる最小値を 1 行に出力せよ. 書き換えが行われる前の数値は全て 0 以上 n 未満であったことに注意されたい.

Sample Input

2
1 0
1 1
3
2 2
2 0
0 1
4
0 3
0 2
3 1
2 0
5
0 3
0 3
1 2
4 2
4 2
3
1 1
2 2
2 2
4
0 0
1 1
2 2
3 3
0

Output for the Sample Input

1
1
0
1
2
4
(End of Problem E) A B C D E F G H