#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

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.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le t \le 10^9$
$1 \le a_i \le 10^9$

Input

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

Output

time_{\min}

Samples

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.

$1 \le n \le 2 \cdot 10^5$
$1 \le t \le 10^9$
$1 \le a_i \le 10^9$

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

time_{\min}