Máy sản xuất (Factory Machines)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một nhà máy có $n$ máy. Máy thứ $i$ cần đúng $k_i$ giây để hoàn thành một sản phẩm. Sau khi hoàn thành, máy có thể lập tức bắt đầu sản phẩm tiếp theo. Các máy hoạt động độc lập và đồng thời; chỉ sản phẩm đã hoàn thành mới được tính.

Hãy tìm thời gian nguyên nhỏ nhất để tổng số sản phẩm làm ra đạt ít nhất $t$.

Input

Dòng đầu chứa $n$ và $t$. Dòng tiếp theo chứa $k_1,k_2,\ldots,k_n$.

Output

In thời gian nhỏ nhất cần thiết.

Subtask

• Subtask 1 — 20%: $n=1$.
• Subtask 2 — 30%: $1\le n\le1000$, $1\le t\le10^6$.
• Subtask 3 — 50%: $1\le n\le2\cdot10^5$, $1\le t\le10^9$, $1\le k_i\le10^9$.

Ví dụ

Input

3 7
3 2 5

Output

8

Giải thích

Sau $8$ giây, ba máy làm lần lượt $2$, $4$ và $1$ sản phẩm, tổng cộng $7$ sản phẩm.