Trong các môn thi đấu đối kháng hai người như bóng bàn, cầu lông, cờ vua, hai thể thức thi đấu phổ biến nhất là loại trực tiếp và vòng tròn. Thể thức thứ nhất có ưu điểm là số trận đấu ít, trận nào cũng căng thẳng hấp dẫn, nhưng tính may rủi khá cao. Thể thức thứ hai công bằng hơn, tính may rủi thấp hơn, nhưng quá trình thi đấu thường rất kéo dài.

Thể thức đấu vòng Thụy Sĩ được giới thiệu trong bài này có tên gọi như vậy vì được sử dụng lần đầu tại giải cờ vua tổ chức ở Thụy Sĩ năm 1895. Nó có thể coi là sự dung hòa giữa loại trực tiếp và vòng tròn, vừa bảo đảm tính ổn định của giải đấu, vừa không làm lịch thi đấu quá dài.

$2 \times N$ tuyển thủ được đánh số $1\sim 2\times N$ thi đấu tổng cộng $R$ vòng. Trước khi mỗi vòng bắt đầu, cũng như sau khi toàn bộ các trận kết thúc, các tuyển thủ đều được xếp hạng một lần theo tổng điểm từ cao xuống thấp. Tổng điểm của một tuyển thủ bằng điểm ban đầu trước vòng thứ nhất cộng với tổng điểm giành được ở tất cả các trận đã đấu. Nếu tổng điểm bằng nhau, quy ước tuyển thủ có số hiệu nhỏ hơn được xếp trên.

Việc sắp xếp cặp đấu của mỗi vòng phụ thuộc vào bảng xếp hạng trước khi vòng đó bắt đầu: hạng $1$ gặp hạng $2$, hạng $3$ gặp hạng $4$, ……, hạng $2\times K - 1 $ gặp hạng $2\times K$, ……, hạng $2\times N - 1$ gặp hạng $2\times N$, mỗi cặp thi đấu một trận. Trong mỗi trận, người thắng được $1$ điểm, người thua được $0$ điểm. Nói cách khác, ngoại trừ vòng đầu tiên, cặp đấu của các vòng còn lại không thể xác định trước mà phụ thuộc vào thành tích của các tuyển thủ trong những trận trước đó.

Cho điểm ban đầu và giá trị thực lực của từng tuyển thủ, hãy tính xem sau $R$ vòng đấu, tuyển thủ xếp hạng $Q$ mang số hiệu bao nhiêu. Ta giả sử giá trị thực lực của các tuyển thủ đôi một khác nhau, và trong mỗi trận đấu, người có thực lực cao hơn luôn thắng.

Dữ liệu vào

Dòng đầu tiên gồm ba số nguyên dương $N,R,Q$, hai số liền nhau cách nhau một dấu cách, cho biết có $2\times N $ tuyển thủ, $R$ vòng đấu và thứ hạng $Q$ mà ta quan tâm.

Dòng thứ hai gồm $2\times N$ số nguyên không âm $s_1, s_2,\dots, s_{2\times N}$, hai số liền nhau cách nhau một dấu cách, trong đó $s_i $ là điểm ban đầu của tuyển thủ mang số hiệu $i$.

Dòng thứ ba gồm $2\times N$ số nguyên dương $w_1,w_2,\dots,w_{2\times N}$, hai số liền nhau cách nhau một dấu cách, trong đó $w_i$ là giá trị thực lực của tuyển thủ mang số hiệu $i$.

Dữ liệu ra

Một số nguyên, là số hiệu của tuyển thủ xếp hạng $Q$ sau khi $R$ vòng đấu kết thúc.

Ví dụ

Input

2 4 2 
7 6 6 7 
10 5 20 15

Output

1

Ghi chú

Giải thích ví dụ

Phạm vi dữ liệu

Với $30\%$ số dữ liệu, $1\le N\le 100$;

Với $50\%$ số dữ liệu, $1\le N\le 10000$;

Với $100\%$ số dữ liệu, $1\le N\le 10^5,1\le R\le 50,1\le Q\le 2\times N,0\le s_1, s_2,\dots,s_{2\times N}\le 10^8,1\le w_1, w_2 , \dots, w_{2\times N}\le 10^8$.

Nguồn: bài 3 bảng phổ cập NOIP 2011.