Minimum Production Time - Classic Problems | Repovive

CLS56. Minimum Production Time

2s256 MB

There are $n$ machines. Machine $i$ produces one item every $a_i$ seconds. Find the minimum time needed to produce at least $t$ items.

\begin{array}{l} n \quad t \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

time_{\min}

Input

3 7
3 2 5

Explanation

At time 8, the machines produce 2 + 4 + 1 = 7 items, and no earlier time reaches 7.

Output

Input

1 10
4

Explanation

One machine producing every 4 seconds needs 40 seconds for 10 items.

Output

Input

4 12
5 5 5 5

Explanation

At time 15, the four machines produce 12 total items.

Output

There are $n$ machines. Machine $i$ produces one item every $a_i$ seconds. Find the minimum time needed to produce at least $t$ items.

\begin{array}{l} n \quad t \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

time_{\min}