Maximum Storage Utilization

You are given a warehouse with a storage capacity ( c ) and ( n ) different product types. Each product type occupies a specific storage space given by ( s_i ) for ( i=1,2,...,n ). You may select an unlimited number of each product type (i.e. unbounded quantity) as long as the total storage used does not exceed the capacity ( c ).

Your task is to compute the maximum storage that can be utilized without exceeding the warehouse capacity. Formally, for non-negative integers ( k_i ) (where ( k_i ) is the quantity of the ( i^{th} ) product) you need to maximize the sum ( \sum_{i=1}^{n} k_i s_i ) subject to the constraint ( \sum_{i=1}^{n} k_i s_i \leq c ).

The problem can be solved using the unbounded knapsack (complete knapsack) dynamic programming approach.

inputFormat

The input consists of multiple datasets. Each dataset begins with a line containing two integers ( n ) and ( c ) representing the number of product types and the warehouse capacity, respectively. This is followed by ( n ) lines, each containing one integer representing the storage space required by a product type. The input terminates with a line containing a single zero.

outputFormat

For each dataset, output one line containing the maximum storage space that can be utilized without exceeding the capacity.## sample

3 50
10
20
30
2 5
3
8
0

50
3