Maximum Weekly Allowance Partition

Farmer John wants to reward Bessie for setting a milk production record by giving her a weekly allowance. He has a collection of coins in \(N\) different denominations, where \(N\) is in the range \(1 \le N \le 20\). Moreover, each coin denomination divides every coin with a larger denomination. Each week, Farmer John must pay Bessie at least an allowance of \(C\) (\(1 \le C \le 100000000\)) by selecting some of the coins from his collection. Each coin can be used at most once. The task is to determine the maximum number of weeks for which he can pay Bessie her allowance.

Note: The coins must be partitioned into groups so that the sum in each group is at least \(C\). The denominations satisfy the property that for any two denominations \(d_i\) and \(d_j\) with \(d_i < d_j\), it holds that \(d_i\) divides \(d_j\).

inputFormat

The input consists of two lines.

• The first line contains two integers: \(N\) and \(C\), representing the number of coin denominations and the minimum required allowance per week respectively.
• The second line contains \(N\) positive integers, representing the values of the coins. The coins may be given in any order, but they satisfy the property that each coin denomination divides every coin of higher value.

outputFormat

Output a single integer: the maximum number of weeks Farmer John can pay Bessie at least \(C\) using all of the coins (each coin can be used at most once).

sample

3 7
1 2 8

1