Máy cưa gỗ (EKO)

Nguồn: SPOJ

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

Đề bài

Có $N$ cây với chiều cao $h_i$. Đặt lưỡi cưa ở độ cao nguyên $H$: cây cao hơn $H$ bị cắt phần phía trên $H$, còn cây không cao hơn $H$ giữ nguyên.

Tổng lượng gỗ thu được là:

Cần lấy ít nhất $M$ đơn vị gỗ nhưng muốn đặt lưỡi cưa cao nhất có thể. Hãy tìm $H$ lớn nhất vẫn thu được ít nhất $M$.

Input

Dòng đầu chứa $N,M$. Dòng sau chứa $N$ chiều cao cây.

Output

In độ cao lưỡi cưa lớn nhất.

Subtask

• Subtask 1 — 20%: $1\le N\le1000$.
• Subtask 2 — 30%: $1\le N\le10^5$.
• Subtask 3 — 50%: $1\le N\le10^6$, $1\le M\le2\cdot10^9$, $1\le h_i<10^9$. Tổng các chiều cao lớn hơn $M$.

Ví dụ

Input

4 7
20 15 10 17

Output

15

Giải thích

Ở $H=15$, lượng gỗ thu được là $(20-15)+(17-15)=7$. Nếu nâng lên $16$, chỉ thu được $4+1=5<7$, nên đáp án là $15$.