Factory Machines

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

A factory has $n$ machines. Machine $i$ needs exactly $k_i$ seconds to complete one product. After finishing a product, it may immediately start the next one. All machines work independently and simultaneously, and only completed products are counted. Find the minimum integer time required to produce at least $t$ products.

Input

The first line contains $n$ and $t$. The second line contains $k_1,\ldots,k_n$.

Output

Print the minimum required time.

Subtasks

• 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$.

Examples

Input

3 7
3 2 5

Output

8

Explanation

After $8$ seconds the machines produce $2+4+1=7$ products.