Contest(コンテスト) - joi2009-day2

出典: 第8回日本情報オリンピック 春季トレーニング合宿

時間制限: 1秒

メモリ制限: 64MB

先日, とある国際的なプログラミングコンテストが開かれ, Nヶ国が参加した. コンテストに参加したNヶ国にはそれぞれ, 1, 2, … , N の番号がつけられている.

このコンテストには, 各国から2人の選手が派遣された. 各選手ごとに競技の点数がつけられ, 派遣した2人の選手の得点の和が国の得点となる. そして, 得点の大きい国から順に1 位, 2位…と順位がつけられる. ただし, いくつかの国が同点となった場合は, それらの国には同じ順位がつけられる. より正確には, ある国の順位は, その国より高い得点をとった国の数に1を足したものである. たとえば, 競技が4ヶ国で行われ, 各国の得点がそれぞれ100,90,90,80だった場合, 100点の国は1位, 90点の国の順位は両方とも2位, 80点の国は4位となる.

今回このコンテストの運営に携わっているX氏は, あるとき, 不注意により競技の得点のデータの一部を紛失してしまった. その結果, 得点の値はすべての参加者の分が残っているが, 一部の得点についてはどの国の参加者のものかがわからないという状況になってしまった.

困り果てているX氏のもとに, 参加国の1つから順位の問い合わせがあった. 残念ながらデータの紛失により正確な順位はわからないので, X氏は問い合わせに対して, 残っているデータから考えられる最高の順位を答えることにした. そこで, 得点のデータが与えられたとき, 指定された国の考えられる最高順位を出力するプログラムを作れ.

Input.

入力ファイルcontest.inの1行目には, 2つの整数N,C(1 ≤ N ≤ 3000, 1 ≤ C ≤ N) が空白を区切りとして書かれている. Nはコンテストに参加した国の数を, Cは順位の問い合わせがあった国の番号を表す.

続く2N行はコンテストの得点のデータを表す. i+1行目(1 ≤ i ≤ 2N) には2つの整数s[i],a[i](0 ≤ s[i] ≤ 1 000 000(= 10^6); 0 ≤ a[i] ≤ N) が空白を区切りとして書かれており, これはそのデータが番号a[i]の国の参加者のもので, 得点がs[i]であることを表す. ただしa[i] = 0 の場合は, そのデータがどの国の参加者のものかがわからないことを表す.

Output.

出力は, 標準出力に行うこと. 番号Cの国の順位として考えられる最高の順位(数値としてもっとも小さい値) を表す1つの整数を出力せよ.

例

contest.in 標準出力
3 1
7 0
3 1
5 0
10 3
6 0
4 0		 2

この場合, 国1の順位としては次のように2位または3位が考えられるので, 2を出力する: