Trung vị lớn nhất (Maximum Median)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng $a$ gồm $n$ số nguyên, với $n$ lẻ. Một thao tác chọn một phần tử và tăng nó thêm $1$. Được thực hiện nhiều nhất $k$ thao tác.

Trung vị của mảng lẻ phần tử là phần tử đứng giữa sau khi sắp không giảm. Hãy làm trung vị lớn nhất có thể.

Input

Dòng đầu chứa $n,k$. Dòng thứ hai chứa $a_1,\ldots,a_n$.

Output

In trung vị lớn nhất có thể.

Subtask

• Subtask 1 — 20%: $n\le100$.
• Subtask 2 — 30%: $n\le5000$.
• Subtask 3 — 50%: $1\le n\le2\cdot10^5$, $n$ lẻ, $1\le k\le10^9$, $1\le a_i\le10^9$.

Ví dụ

Input

5 5
1 2 1 1 1

Output

3

Giải thích

Sau khi sắp là $[1,1,1,1,2]$. Dùng các lần tăng để nâng ba phần tử từ vị trí trung vị trở về sau đủ để trung vị đạt $3$, nhưng không đủ để đạt $4$.