## WC '17 Contest 1 S4 - Change

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
##### Woburn Challenge 2017-18 Round 1 - Senior Division

Your friend is just getting into competitive programming, and is trying to solve the classic "change" problem. You'll give him a target value and some distinct coin denominations (each of which is between and , inclusive), and he'll try to determine whether or not a total of can be produced using a set of (possibly duplicate) coins having only those denominations. The algorithm he's come up with to do so is greedy - starting from an empty set of coins, it repeatedly adds on the largest possible coin which won't cause the total to exceed , until it either reaches a total of , or is unable to add on any more coins and gives up.

You're not sure what coin denominations you'd like to give him, but there are distinct denominations which you definitely don't want to include. The of these is .

Your friend is convinced that his algorithm is so good that he'll be able to attain a total of no matter what denominations he's given! This is quite the bold claim. You'd like to prove him wrong by choosing a (possibly empty) set of denominations such that his algorithm will fail to reach a total of using them. Note that it doesn't matter whether or not a more correct algorithm would succeed, as long as your friend's greedy algorithm fails to achieve a total of .

Clearly, one option would be to simply give your friend denominations to use. However, that's too easy - you'd like to prove as convincingly as possible that their algorithm is sub-par. As such, you'd like to determine the maximum number of distinct denominations which you can give your friend, such that their algorithm will still fail to reach a total of using them.

In test cases worth of the points, .
In test cases worth another of the points, .

#### Input Specification

The first line of input consists of two space-separated integers, and .
lines follow, the of which consists of a single integer, , for .

#### Output Specification

Output a single integer, the maximum number of distinct denominations which you can give your friend.

#### Sample Input 1

7 4
3 7 6 1

#### Sample Output 1

2

#### Sample Input 2

4 1
3

#### Sample Output 2

0

#### Sample Explanation 2

In the first case, one possibility is to give your friend the set of denominations . His algorithm would use a coin followed by a coin, and then give up.

In the second case, you must resort to giving your friend no denominations, as his algorithm would achieve a total of if given any non-empty subset of the denominations .