시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB46231546.875%

문제

時は 21XX 年,競技プログラミングはマインドスポーツの 1 つとして広く認知されており,テレビ,新 聞などのメディアで取り上げられることも多い.

あなたは JOI 新聞社の記者であり,競技プログラミングの記事を担当している.

昨日,N 人の選手による国際的な競技プログラミングのコンテストが開催された.このコンテストにつ いての記事を書くために,あなたには次の情報が与えられた.

  • 国際情報オリンピックなどと同様,このコンテストにはいくつかの国から選手が参加した.国には 1 から N までのいずれかの番号が付けられている.一つの国から複数の選手が参加することもあり得 る.また,選手が参加しない国があるかもしれない.
  • このコンテストの競技時間は 5 時間である.
  • コンテスト中に選手の獲得した点数が,その後減らされることはない.
  • コンテスト開始後 2 時間経過した時点において,同点の選手はいなかった.その時点の順位表におい て,i 位 (1 ≦ i ≦ N) の選手は国 Ai の出身で,その選手の点数は Bi 点であった.
  • コンテスト終了時点において,同点の選手はいなかった.コンテスト終了時点の順位表において,i 位 (1 ≦ i ≦ N) の選手は国 Ci の出身で,その選手の点数は Di 点であった.

しかしながら,記事を書く段階になって,順位表の出身国の表示に不具合があったことが判明した.選 手の出身国の情報が間違って表示されていた可能性がある.表示されていた選手の点数は正しいことが分 かっている.

そこで,あなたは,与えられた情報にできるだけ少ない修正を加えることで,順位表の情報として矛盾 のない (同じ選手の出身国がコンテスト中に変わったり,選手の獲得した点数がコンテスト中に減少したり しない) ものを推測することにした.すなわち,2N 個の値 A1, . . . , AN, C1, . . . ,CN のうちのできるだけ少な い箇所を変更することで,次の条件を満たすようにしたい:

  • 1, 2, . . . , N のある並び替え x1, x2, . . . , xN であって,各 i = 1, 2, . . . , N に対して Ai = Cxi かつ Bi ≦ Dxi が成り立つものが存在する.

あなたは,与えられた情報に,最少で何箇所の修正を加える必要があるだろうか.

コンテストの参加者数と,コンテスト開始後 2 時間経過した時点とコンテスト終了時点の順位表につい ての情報が与えられたとき,順位表を矛盾のない状態にするために必要な,出身国情報の変更箇所の個数 の最小値を求めるプログラムを作成せよ.

입력

標準入力から以下のデータを読み込め.

  • 1 行目には,整数 N が書かれている.これは,コンテストに N 人の選手が参加したことを表す.
  • 続く N 行のうちの i 行目 (1 ≦ i ≦ N) には,整数 Ai, Bi が空白を区切りとして書かれている.これは, コンテスト開始後 2 時間経過した時点の順位表において,i 位の選手は国 Ai 出身と表示され,獲得し た点数は Bi 点であったことを表す.
  • 続く N 行のうちの i 行目 (1 ≦ i ≦ N) には,整数 Ci, Di が空白を区切りとして書かれている.これは, コンテスト終了時点の順位表において,i 位の選手は国 Ci 出身と表示され,獲得した点数は Di 点で あったことを表す.

출력

標準出力に,順位表を矛盾のない状態にするために必要な,出身国情報の変更箇所の個数の最小値を 1 行で出力せよ.

제한

  • 2 ≦ N ≦ 200 000.
  • 1 ≦ Ai ≦ N (1 ≦ i ≦ N).
  • 0 ≦ Bi ≦ 1 000 000 000 (1 ≦ i ≦ N).
  • Bi > Bi+1 (1 ≦ i ≦ N − 1).
  • 1 ≦ Ci ≦ N (1 ≦ i ≦ N).
  • 0 ≦ Di ≦ 1 000 000 000 (1 ≦ i ≦ N).
  • Di > Di+1 (1 ≦ i ≦ N − 1).
  • A1, . . . , AN, C1, . . . ,CN の値を何箇所か変更することにより,順位表を矛盾のない状態にすることがで きる.

서브태스크

번호배점제한
115

N ≦ 16 を満たす.

215

N ≦ 50 を満たす.

330

N ≦ 5000 を満たす.

440

追加の制約はない.

예제 입력 1

3
3 500
2 200
1 100
1 1000
3 700
3 400

예제 출력 1

1

C3 の値を 2 に修正すると,次のように矛盾のない順位表になる:

  • コンテスト開始後 2 時間経過した時点において 500 点で 1 位だった国 3 出身の選手は,コンテスト 終了時点において 700 点で 2 位となった.
  • コンテスト開始後 2 時間経過した時点において 200 点で 2 位だった国 2 出身の選手は,コンテスト 終了時点において 400 点で 3 位となった.
  • コンテスト開始後 2 時間経過した時点において 100 点で 3 位だった国 1 出身の選手は,コンテスト 終了時点において 1000 点で 1 位となった.

ここで,C2 の値を 2 に修正した場合,国 3 出身の選手がコンテスト開始後 2 時間経過した時点において 500 点を獲得しているにも関わらず,コンテスト終了時点において 400 点となっているため,矛盾した順 位表となる.

1 箇所より少ない修正によって矛盾のない順位表を得ることは不可能であるから,1 を出力する.

예제 입력 2

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

예제 출력 2

0

この場合,出身国情報を修正しなくても矛盾のない順位表となっている.コンテスト開始後 2 時間経過 した時点の点数から点数を増やしていない選手が存在するかもしれないことに注意せよ.また,順位表に おいて,同じ出身国の選手が複数いる可能性があることに注意せよ.

예제 입력 3

6
1 70
4 50
1 30
2 20
1 10
3 0
6 100
2 90
1 80
2 60
4 40
1 10

예제 출력 3

3

この入力例において,A1 の値を 2 に修正し,A6 の値を 4 に修正し,C1 の値を 4 に修正すると,矛盾の ない順位表になる.

채점 및 기타 정보

  • 예제는 채점하지 않는다.