舞踏会 (Ball)

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

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

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

貴族 1 から貴族 M (1 ≤ MN − 2) の M 人の貴族については,すでに初期状態で列の何番目に並ぶのかが決まっている.残りの NM 人の貴族の並び方は国王が自由に決めることができる.

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

課題

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

入力

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

出力

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

制限

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

入出力例

入力例 1

7 3
5 2
5 5
8 6
6
2
8
9

出力例 1

8

初期状態では 3 人の貴族の並ぶ場所がすでに決まっている.


括弧内の数字は踊りのうまさを表す.左端が列の先頭である.

例えば,先頭から順に貴族 5,貴族 1,貴族 4,貴族 6,貴族 2,貴族 3,貴族 7 という順番に並んだ場 合を考える.


すべての貴族が並んだあとの配置

この場合,以下のように列が変化していく.


列の変化の様子

入力例 2

3 1
5 3
5
5

出力例 2

5

どのような順番で並んでも,貴族 2 と JOI 姫が組になる.

入力例 3

7 2
32 4
27 6
37
41
41
30
27

出力例 3

37

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。