Thời gian hoàn thành lô sản phẩm

Bối cảnh và bài toán

Một nhà máy có n máy hoạt động song song. Máy i cần k[i] giây để hoàn thành một sản phẩm và có thể lặp lại liên tục. Nhà máy cần biết thời gian nhỏ nhất để tổng số sản phẩm hoàn thành đạt ít nhất t.

Yêu cầu

Tìm thời gian nguyên nhỏ nhất đủ để các máy hoàn thành ít nhất t sản phẩm.

Input

• Dòng 1: n t.
• Dòng 2: n thời gian k[i].

Output

In thời gian nhỏ nhất.

Ràng buộc

• 1 <= n <= 2 * 10^5
• 1 <= t <= 10^9
• 1 <= k[i] <= 10^9

Chấm điểm

Ví dụ 1

Input

3 7
3 2 5

Output

8

Giải thích. Trong 8 giây, ba máy tạo lần lượt 2, 4 và 1 sản phẩm, tổng đúng 7.

Ví dụ 2

Input

2 10
1 1

Output

5

Giải thích. Hai máy mỗi giây tạo tổng cộng hai sản phẩm; sau 5 giây có 10 sản phẩm.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Factory Machines (Task 1620).

Tham khảo: https://www.cses.fi/problemset/task/1620/