401520: GYM100488 G Change-making Problem

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Change-making Problemtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are types of coins in the country R, the cheapest of which has denomination 1 and each of the next types has denomination ai times greater than the previous one. You need to pay the sum s using as few coins as possible. Of course you can use multiple coins of the same denomination.

Input

The first line contains two integers separated by a space: n and s (1 ≤ n ≤ 105, 0 ≤ s ≤ 109) —- the number of coins' types, excluding the cheapest one, and the sum to pay.

The second line contains n integers separated by spaces: ai (2 ≤ ai ≤ 109) — the number of times each of the next coins is more expensive than the previous one.

Output

Output a single integer — the minimum number of coins required to pay the sum s.

ExamplesInput
3 42
3 2 2
Output
4
Input
5 228
5 2 5 2 5
Output
8

加入题单

上一题 下一题 算法标签: