D. POOL - Bể bơi

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Nguồn: Ôn HN tháng 11/2017, Thầy Lê Minh Hoàng, Ngày 1

Trường tiểu học SuperKids tổ chức cuộc thi bơi trong một bể bơi chia làm các làn (lane), mỗi vận động viên sẽ phải bơi từ đầu tới cuối bể theo một làn được xếp cho vận động viên đó. Có 𝑛 học sinh đánh số từ 1 tới 𝑛 tham gia cuộc thi, biết rằng học sinh thứ 𝑖 có thể thực hiện bài thi trong 𝑡_𝑖 giây.

Ban tổ chức muốn chia bể bơi thành 𝑘 làn và cách thức thi dự định sẽ diễn ra như sau: Ban đầu 𝑘 học sinh từ 1 tới 𝑘 cùng xuất phát, mỗi học sinh một làn. Mỗi khi một học sinh thực hiện xong bài thi, học sinh kế tiếp (học sinh có số hiệu nhỏ nhất trong số những người chưa bơi) sẽ xuất phát ngay ở làn bơi của học sinh vừa thi xong…

Do giới hạn thời gian, cuộc thi không thể diễn ra trong thời gian quá 𝑚 giây (tính lúc bắt đầu cho tới khi tất cả vận động viên đã thi xong), mặt khác nếu chia bể bơi làm quá nhiều làn, các vận động viên sẽ bị ảnh hưởng nhiều do sóng và khán giả cũng khó theo dõi cuộc thi. Hãy giúp ban tổ chức tìm số 𝑘 nhỏ nhất để nếu chia bể bơi thành 𝑘 làn thì cuộc thi diễn ra không quá 𝑚 giây.

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương 𝑛 ≤ 10^5; 𝑚 ≤ 10^9 ;
  • Dòng thứ hai chứa 𝑛 số nguyên dương 𝑡_1, 𝑡_2, … , 𝑡_𝑛\ (∀𝑖: 𝑡_𝑖 ≤ 𝑚) .

Các số trên một dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là số 𝑘 tìm được.

Ví dụ:

Dữ liệu vào:
5 8
4 7 8 6 4
Dữ liệu ra:
4