舞踏会 (Ball)

IOI 王国では，王女である JOI 姫の誕生日を祝って舞踏会が開かれることになった．

舞踏会には \(N\) 人の貴族が参加する予定である．\(N\) は奇数である．貴族には \(1\) から \(N\) までの番号が付けられている．それぞれの貴族には踊りのうまさという整数が定められており，貴族 \(i\) (\(1 \leqq i \leqq N\)) の踊りのうまさは \(D_i\) である．

舞踏会では JOI 姫を含む \(N + 1\) 人で \(2\) 人ずつ組を作って踊る．IOI 王国では，上級者が初級者を補助できるように，伝統的に以下の方法で踊りの組を決定している．

• 最初に，\(N\) 人の貴族が \(1\) 列に並ぶ．
• 列に並んでいる貴族が \(1\) 人になるまで，以下の操作を繰り返す．
  • 列の先頭から \(3\) 人の貴族の踊りのうまさを調べる．
  • その \(3\) 人の貴族の中で，最も踊りのうまさが大きい貴族を \(A\) とおく．ただし，複数いる場合は，最も踊りのうまさが大きい貴族の中で，最も番号の小さい貴族 を \(A\) とおく．
  • その \(3\) 人の貴族の中で，最も踊りのうまさが小さい貴族を \(B\) とおく．ただし，複数いる場合は，最も踊りのうまさが小さい貴族の中で，最も番号の大きい貴族 を \(B\) とおく．
  • \(A\) と \(B\) が列から抜けて組になる．
  • 残った \(1\) 人は列の最後尾に移動する．
• 最終的に残った \(1\) 人が JOI 姫と組になる．貴族 \(1\) から貴族 \(M\) (\(1 \leqq M \leqq N - 2\)) の \(M\) 人の貴族については，すでに初期状態で列の何番目に並ぶのかが決まっている．残りの \(N - M\) 人の貴族の並び方は国王が自由に決めることができる．

JOI 姫は踊りを学んだばかりなので，国王は JOI 姫と組になる貴族の踊りのうまさをできるだけ大きくしたいと考えている．JOI 姫と組になる貴族の踊りのうまさとして考えられる最大値を求めよ．

課題

それぞれの貴族の踊りのうまさと，\(M\) 人の貴族の初期状態で並ぶ場所が与えられたとき，JOI 姫と組になる貴族の踊りのうまさとして考えられる最大値を求めるプログラムを作成せよ．

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

• \(1\) 行目には，\(2\) 個の整数 \(N, M\) が空白を区切りとして書かれている．これは舞踏会に貴族が \(N\) 人参加し，列に並ぶ場所がすでに決まっている貴族が \(M\) 人いることを表す．
• 続く \(M\) 行のうちの \(i\) 行目 (\(1 \leqq i \leqq M\)) には，\(2\) 個の整数 \(D_i, P_i\) が空白を区切りとして書かれている．これは貴族 \(i\) の踊りのうまさが \(D_i\) で，貴族 \(i\) が初期状態で列の先頭から \(P_i\) 番目に並ぶことを表す．
• 続く \(N - M\) 行のうちの \(i\) 行目 (\(1 \leqq i \leqq N - M\)) には，整数 \(D_{i + M}\) が書かれている．これは貴族 (\(i + M\)) の踊りのうまさが \(D_{i + M}\) であることを表す．

標準出力に，JOI 姫と組になる貴族の踊りのうまさとして考えられる最大値を表す整数を \(1\) 行で出力せよ．

すべての入力データは以下の条件を満たす．

• \(3 \leqq N \leqq 99\,999\)．
• \(N\) は奇数である．
• \(1 \leqq M \leqq N - 2\)．
• \(1 \leqq D_i \leqq 1\,000\,000\,000\) (\(1 \leqq i \leqq N\))．
• \(1 \leqq P_i \leqq N\) (\(1 \leqq i \leqq M\))．
• \(P_i \neq P_j\) (\(1 \leqq i < j \leqq M\))．

小課題 1 [8 点]

• \(N \leqq 9\) を満たす．

小課題 2 [16 点]

• \(N \leqq 19\) を満たす．

小課題 3 [44 点]

• \(N \leqq 1\,999\) を満たす．

小課題 4 [32 点]

追加の制限はない．

JOI 2015 · JCIOI · CC BY-SA 4.0