24132번 - コンテスト (Contest) 다국어

先日，とある国際的なプログラミングコンテストが開かれ，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 氏は問い合わせに対して，残っているデータ から考えられる最高の順位を答えることにした．そこで，得点のデータが与えられたとき，指 定された国の考えられる最高順位を出力するプログラムを作れ．

入力の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⁶), 0 ≤ a_i ≤ N) が空白を区切りとして書かれており，これはその データが番号 a_i の国の参加者のもので，得点が s_i であることを表す．ただし a_i = 0 の場合は， そのデータがどの国の参加者のものかがわからないことを表す．

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

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

• 7 点のデータが国 1 のもので，5 点のデータと 4 点のデータが国 2 のもの，6 点のデータが 国 3 のものの場合，国 1 の得点は 7+3=10，国 2 の得点は 5+4=9，国 3 の得点は 10+6=16 となり，国 1 の順位は 2 位となる．
• 7 点のデータが国 1 のもので，5 点のデータと 6 点のデータが国 2 のもの，4 点のデータが 国3のものの場合，国1の得点は7+3=10，国2の得点は5+6=11，国3の得点は10+4=14 となり，国 1 の順位は 3 位となる．