BÀI TẬP 9 [C++]: NHÀ MÁY SẢN XUẤT

Một nhà máy có N máy móc có thể được sử dụng để sản xuất sản phẩm. Mục tiêu của bạn là kiếm được tổng cộng t sản phẩm.

            Đối với mỗi máy, bạn biết được số giây cần thiết để tạo ra một sản phẩm. Các máy có thể hoạt động đồng thời và bạn có thể tự quyết định lịch trình của chúng.

            Thời gian ngắn nhất cần thiết để làm ra t sản phẩm?

Dữ liệu vào:

- Dòng đầu tiên có hai số nguyên N và t (1 ≤ N ≤ 2.10⁵; 1 ≤ t ≤ 10⁹): số lượng máy móc, sản phẩm.

- Dòng tiếp theo có N số nguyên k₁, k₂, …, k_{N (}1 ≤ k_i ≤ 10⁹) thời gian cần thiết để tạo ra một sản phẩm sử dụng mỗi máy.

Dữ liệu ra: In một số nguyên: thời gian tối thiểu cần thiết để thực hiện t sản phẩm.

Ví dụ:

Input	Output
3 7 3 2 5	8

Giải thích: Máy 1 làm được 2 sản phẩm, máy 2 làm được 4 sản phẩm và máy 3 làm được 1 sản phẩm.