401520: GYM100488 G Change-making Problem

There are types of coins in the country R, the cheapest of which has denomination 1 and each of the next types has denomination a_i 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.

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

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

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

3 42
3 2 2

4

5 228
5 2 5 2 5

8