This page is still under construction.

Parts of this page are still being built. What you see may change.

Vending Machine

Interview

Time limit8sMemory limit512 MB

Summary
Given up to 10 coin denominations and a target M up to 100000, find the minimum number of operations where each operation outputs at most one coin of each denomination.
Level

Medium6 of 10

Topics
Dynamic programming, Greedy, Math, Implementation
Solved
No attempts yet

Problem

Beverage vendors have been waging a marketing war, working hard to increase their sales. Kola-Coqua is one of the most successful vendors: its impressive advertisements to the world brought its representative product, Koque, an overwhelming market share.

This time Kola-Coqua is focusing on vending machines. The company believes customers will be happier when the machines respond more quickly, so it has improved many parts of the machines.

In particular, it has developed a new device for returning change. The new device can output one or more kinds of coins in a single operation, but it can output only one coin of each kind per operation. For example, suppose 500-yen, 100-yen, 50-yen, and 10-yen coins are available. Change of 6540 yen can be made with four operations that output a 500-yen and a 10-yen coin and nine operations that output a 500-yen coin. In total, 6540 yen can be returned in thirteen operations. The new device is expected to let customers make their purchases more quickly, which helps Kola-Coqua's market share grow.

However, the project leader says, "It is not optimal yet." His suggestion is this: the real optimization is to minimize the number of operations. For example, change of 6540 yen should be made with ten 500-yen coins, ten 100-yen coins, ten 50-yen coins, and four 10-yen coins. That way, 6540 yen can be returned in only ten operations. This gives the fastest possible change return, even though it sometimes outputs a huge number of coins.

Given which kinds of coins are available and how much change must be returned, write a program that computes the minimum number of operations according to the suggestion above. You may assume the vending machines contain enough coins.

Input

The input consists of multiple data sets. Each data set is given in two lines. The first line contains N (N ≤ 10) and M (M ≤ 100000), the number of kinds of coins and the amount of change to be made. The second line contains N integers, the value of each kind of coin.

The input ends with a data set where N = M = 0. This data set must not be processed.

Output

For each data set, output on one line the minimum number of operations needed to return exactly the specified amount of change.

Examples1

  1. Example 1

    Input
    6 330
1 5 10 50 100 500
7 127
1 2 4 8 16 32 64
2 10000
1000 2000
0 0
    Expected output
    2
1
4