POOL
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ó \(N\) học sinh đánh số từ 1 tới \(N\) tham gia cuộc thi, biết rằng học sinh thứ \(i\) có thể thực hiện bài thi trong \(t[i]\) giây.
Ban tổ chức muốn chia bể bơi thành \(K\) 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 \(K\) 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á \(M\) 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.
Yêu cầu: Tìm số \(K\) nhỏ nhất để nếu chia bể bơi thành \(K\) làn thì cuộc thi diễn ra không quá \(M\) giây.
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương \(N, M (N ≤ 10^5, M ≤ 10^9)\);
Dòng thứ hai chứa \(N\) số nguyên dương \(t[1], t[2], …, t[N], (t[i] ≤ M)\).
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ố \(K\) tìm được.
Sample Input
5 8
4 7 8 6 4
Sample Output
4
Comments
bài khó huhuhu =)))
siuuuuuu
🤫🐧
tao là siêu nhân