Khi mặt trăng lên cao trên bầu trời đen tối, một không gian ma quái và huyền bí bao phủ lên khắp nơi. Gió lạnh thoảng qua những cành cây khô héo, tạo nên âm thanh u ám và hồi hộp xao lạc lòng người.
Halloween - một đêm của những điều kỳ dị, nơi giới hạn giữa thế giới thực và thế giới ma quỷ trở nên mờ nhạt. Đó là thời điểm mà mọi người tạm quên đi cuộc sống hàng ngày và để mình trở thành những nhân vật ma quái trong câu chuyện của riêng mình. Nó là một đêm để hòa mình vào không gian ma thuật và khám phá những điều bí ẩn của thế giới đêm tối.
Cánh cửa cũ kỹ mở ra, tiếng "cót két cót két..." cất lên như lời thách thức từ thế giới bên kia. Những ánh đèn mờ ảo, màu tím và cam, phát sáng từ bên trong ngôi nhà hoang tàn, tạo nên cảm giác bí ẩn và hấp dẫn. Những chiếc mặt nạ quỷ dữ, phù thủy và ma cà rồng trang trí khắp mọi nơi. Quả bí ngô được khắc họa với khuôn mặt ma quỷ và đèn lồng hình ma cà rồng lấp lánh, tạo nên ánh sáng lạnh lùng và sự sợ hãi. Đám trẻ thích thú nhảy nhót và trò chuyện vui vẻ trong những bộ trang phục đầy sáng tạo, chờ đợi giờ đi lùng sục kẹo ngọt từ cửa nhà này đến cửa nhà khác.
Trong đêm Halloween, bạn bè và gia đình tụ họp để chia sẻ những câu chuyện rùng rợn, xem phim kinh dị và tham gia vào các trò chơi đặc biệt chỉ xuất hiện vào ngày này. Trong trò chơi đặc biệt năm nay, mỗi người chơi được cung cấp ~n~ số nguyên ~a_{1}, a_{2}, \dots, a_{n}~ và một số nguyên dương ~m~.
Mỗi lượt chơi, người chơi có quyền chọn (hoặc không chọn) các số trong dãy ~a~ theo bất kì tự nào và mỗi số chỉ được chọn một lần trong suốt trò chơi. Ví dụ, ở lượt chơi thứ ~i~, người chơi chọn ~j~ số nguyên ~b_{1}, b_{2}, \dots, b_{j}~ thì sẽ tích được ~\max(b_{1}, 0) + \max(b_{2}-1, 0) + ... + \max(b_{j} - j + 1, 0)~ điểm cho lượt chơi thứ ~i~ (do mỗi số chỉ được chọn một lần nên các số được chọn ở lượt thứ ~i~ sẽ không được chọn lại ở các lượt chơi sau). Trò chơi sẽ kết thúc khi người chơi đạt được ít nhất ~m~ điểm và người chơi chiến thắng là người chơi sử dụng ít lượt chơi nhất.
Vì mỗi người chơi được cung cấp một dãy số riêng biệt nên sự lựa chọn của người chơi này sẽ không ảnh hưởng đến người chơi khác, mặt khác, tuy các dãy số là khác nhau nhưng tính công bằng của trò chơi vẫn được đảm bảo. Tèo rất muốn có được vinh quang của người chiến thắng nên Tèo đã nhờ đến sự trợ giúp của các bạn trẻ ở CLAOJ, hãy giúp Tèo tính toán xem cần ít nhất bao nhiêu lượt chơi để Tèo có thể kết thúc trò chơi.
Dữ liệu vào
- Dòng thứ nhất chứa ~2~ số nguyên dương ~n, m~ ~(1 \le n \le 2 \times 10^{5}, 0 \le m \le 10^{9})~.
- Dòng thứ hai chứ ~n~ số nguyên dương ~a_{1}, a_{2}, \dots, a_{n}~ ~(1 \le a_{i} \le 10^6, 1 \le i \le n)~.
Kết quả ra
- Một dòng duy nhất chứa số lượt nhỏ nhất để hoàn thành trò chơi. Nếu không thể hoàn thành trò chơi in ra
Impossible
.
Ràng buộc
- Có ~30\%~ số test ứng với ~n \le 5000~.
- Có ~30\%~ số test ứng với ~n \le 10^5, a_{1} + a_{2} + ... + a_{n} = m~.
- Còn lại ~40\%~ số test không có ràng buộc gì thêm.
Ví dụ
Dữ liệu vào
5 29
8 6 8 9 1
Kết quả ra
2
Giải thích
Một trong các cách chọn hợp lệ:
- Ở lượt 1, chọn lần lượt các số
9 8
, số điểm nhận được9 + (8-1) = 16
. - Ở lượt 2, chọn lần lượt các số
6 8 1
, số điểm nhận được6 + (8-1) + max(1-2, 0) = 13
. - Tổng số điểm nhận được sau ~2~ lượt là
29
.
Bình luận