Tại CLAOJ có tổ chức một trò chơi cổng không gian.

Trò chơi có các gian phòng kề nhau được đánh số ~0, 1, 2, \dots, n+1~, trong mỗi phòng ~1, 2, \dots, n~ có một cánh cổng không gian khác nhau. Cánh cổng không gian sẽ đưa người chơi đi tham quan một địa điểm và nhận ~1~ huy hiệu, sau khi chuyến tham quan kết thúc người chơi chỉ được phép chọn dịch chuyển về phòng số ~0~ hoặc ~n+1~.

Khi ở phòng thứ ~i~ người chơi được phép:

• Di chuyển sang phòng bên cạnh với chi phí là ~1~ xu.
• Nếu phòng thứ ~i~ có cổng không gian, đi vào cánh cổng không gian với chi phí ~a_i~ xu.

Bắt đầu trò chơi, người chơi sẽ đứng ở gian phòng số ~0~ và nhận được ~x~ xu. Số huy hiệu đạt được càng nhiều phần thưởng sẽ càng cao.

Yêu cầu: Hãy giúp người chơi tính xem có thể dành được tối đa bao nhiêu huy hiệu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n, x~ ~(1 \le n \le 2\times10^5, 1 \le x \le 10^9)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~, với ~a_i~ chi phí của cánh cổng ở phòng thứ ~i~.

Kết quả ra

• Một dòng duy nhất chứa một số nguyên dương là số huy hiệu tối đa có thể nhận được.

Ràng buộc

• Có ~30\%~ số test ứng với ~1 \le n \le 20~.
• Có ~20\%~ số test ứng với ~20 < n \le 10^4~.
• Còn lại ~50\%~ số test không có ràng buộc gì thêm.

Ví dụ

Dữ liệu vào

6 9
2 1 7 9 7 2 

Kết quả ra

3

Giải thích

Các cổng được chọn ở phòng thứ ~1, 2, 6~.

• Đầu tiên người chơi đi từ cổng $0$ sang $1$ mất $1$ xu, người chơi dịch chuyển từ cổng $1$ sang $0$ mất $2$ xu. Tổng cộng mất ~3~ xu.
• Tiếp theo, người chơi đi từ cổng $0$ sang $2$ mất $2$ xu và dịch chuyển từ cổng $2$ đến cồng $7$ mất $1$ xu. Tổng cộng mất ~3~ xu.
• Cuối cùng, người chơi đi từ cổng $7$ sang $6$ mất $1$ xu và dùng $2$ xu còn lại dịch chuyển đến cổng $0$ hoặc $7$. Tổng cộng mất ~3~ xu.
• Do người chơi dịch chuyển $3$ lần nên nhận được $3$ huy hiệu

Chi phí: 3 + 3 + 3 = 9.