DMPG '16 B5 - Bank Burning

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Bob is now so rich that he has been invited to the exclusive Proletarian Partnership. Everyone in the partnership is so rich that PetaPounds (equivalent to £10^{15}) are used to measure wealth. However, Bob is not satisfied with just being part of the Proletarian Partnership. He wants to be as rich as possible compared to its members.

More specifically, Bob wants to maximize the value of M-W_{avg}, where M is Bob's wealth and W_{avg} is the average wealth of all the members in the partnership, including Bob. In order to accomplish this, Bob has broken into the Central Bank of the Proletarians, which contains the entire life savings of Bob and the N other members of the partnership, each in a separate safe. Each safe is made of high quality mahogany, and thus cannot be opened with brute force. Instead, Bob decides to set the safes on fire (excluding his own, of course), destroying all of the money inside. However, once somebody's safe has been destroyed, they will be considered too poor to be part of the partnership and thus promptly kicked out. Can you help determine the minimum number of safes Bob has to burn?

Input Specification

The first line of input will contain two space-separated integers M (2 \le M \le 1000) and N (2 \le N \le 10^5).

The next N lines will each contain an integer N_i (2 \le N_i \le 1000), the amount of money in the i^\text{th} safe.

For at least 40\% of the marks, 1 \le N \le 1000.

Output Specification

Output a single integer, the minimum number of safes Bob has to destroy to maximize M-W_{avg}.

Sample Input

50 4
100
150
280
10

Sample Output

3

Explanation

Bob must destroy all the safes except the safe with 10 PetaPounds in order to achieve a value of 30 for W_{avg}.


Comments

There are no comments at the moment.