Một kỳ thi lập trình quốc tế có \(N\) quốc gia tham gia, được đánh số từ \(1\) đến \(N\). Mỗi quốc gia cử đúng hai thí sinh. Điểm của một quốc gia là tổng điểm của hai thí sinh thuộc quốc gia đó.

Các quốc gia được xếp hạng theo điểm giảm dần. Những quốc gia bằng điểm có cùng thứ hạng. Cụ thể, thứ hạng của một quốc gia bằng \(1\) cộng với số quốc gia có điểm cao hơn quốc gia đó. Ví dụ, nếu bốn quốc gia có điểm lần lượt là \(100,90,90,80\) thì thứ hạng của họ lần lượt là \(1,2,2,4\).

Ông X, một thành viên ban tổ chức, đã vô tình làm mất một phần dữ liệu. Điểm của tất cả thí sinh vẫn còn, nhưng với một số điểm, không còn biết thí sinh đạt điểm đó thuộc quốc gia nào.

Một quốc gia hỏi ông X về thứ hạng của mình. Do không thể xác định chính xác thứ hạng từ dữ liệu còn lại, ông X quyết định trả lời bằng thứ hạng tốt nhất có thể xảy ra.

Yêu cầu

Cho dữ liệu điểm còn lại và quốc gia \(C\), hãy tìm thứ hạng tốt nhất có thể của quốc gia \(C\). Khi khôi phục các quốc gia bị mất trong dữ liệu, phải giữ nguyên mọi thông tin đã biết và bảo đảm mỗi quốc gia có đúng hai thí sinh.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng thứ nhất chứa hai số nguyên \(N,C\), lần lượt là số quốc gia tham gia và số hiệu quốc gia hỏi về thứ hạng.
• Dòng thứ \(i+1\) (\(1\le i\le2N\)) chứa hai số nguyên \(s_i,a_i\). Thí sinh trong bản ghi này đạt \(s_i\) điểm và thuộc quốc gia \(a_i\). Nếu \(a_i=0\) thì không biết quốc gia của thí sinh đó.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là thứ hạng tốt nhất có thể của quốc gia \(C\), tức giá trị thứ hạng nhỏ nhất phù hợp với dữ liệu còn lại.

Ràng buộc

• \(1\le N\le3000\).
• \(1\le C\le N\).
• \(0\le s_i\le1\,000\,000\).
• \(0\le a_i\le N\).
• Có đúng \(2N\) bản ghi điểm, tương ứng với hai thí sinh của mỗi quốc gia trước khi một phần thông tin quốc gia bị mất.
• Giới hạn thời gian: \(1\) giây cho mỗi test; giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Tổng điểm là \(100\), gồm \(25\) nhóm, mỗi nhóm \(4\) điểm và chứa đúng một test, lần lượt từ 01 đến 25. Không có mức điểm theo ràng buộc bổ sung được công bố.

Ví dụ

3 1
7 0
3 1
5 0
10 3
6 0
4 0

2

Quốc gia \(1\) có thể đứng thứ \(2\) hoặc thứ \(3\):

• Nếu điểm \(7\) thuộc quốc gia \(1\), các điểm \(5\) và \(4\) thuộc quốc gia \(2\), còn điểm \(6\) thuộc quốc gia \(3\), thì tổng điểm ba quốc gia lần lượt là \(7+3=10\), \(5+4=9\), \(10+6=16\). Quốc gia \(1\) đứng thứ \(2\).
• Nếu điểm \(7\) thuộc quốc gia \(1\), các điểm \(5\) và \(6\) thuộc quốc gia \(2\), còn điểm \(4\) thuộc quốc gia \(3\), thì tổng điểm ba quốc gia lần lượt là \(7+3=10\), \(5+6=11\), \(10+4=14\). Quốc gia \(1\) đứng thứ \(3\).

Do đó, thứ hạng tốt nhất cần in là \(2\).