Precise Average

Time limit: 0.08s Memory limit: 64MB Input: Output:

Your friend John works at a shop that sells NN types of products, numbered from 00 to N1N-1.
Product ii has a price of PiP_i bytedollars, where PiP_i is a positive integer.

The government of Byteland has created a new law for shops. The law states that the average of the prices of all products in a shop should be exactly KK, where KK is a positive integer.
John's boss gave him the task to change the prices of the products so the shop would comply with the new law.

He has lots of other stuff to do, so he asked you for help: what is the minimum number of products whose prices should be changed?
A product's price can be changed to any positive integer amount of bytedollars.

Input data

The first line of the input contains two integers NN and KK.
The next line contains NN positive integers, P0,,PN1P_{0}, \, \ldots, \, P_{N-1}.

Output data

Output a single integer between 00 and NN, inclusive: the answer to the question.
It can be proven that it is always possible to change the prices of some products so that the new prices comply with the law.

Constraints and clarifications

  • 1N200 0001 \le N \le 200 \ 000.
  • 1K1061 \le K \le 10^6.
  • 1Pi1061 \le P_i \le 10^6 for each i=0N1i=0\ldots N-1.
  • For tests worth 2020 points, N2N \le 2.
  • For tests worth 2020 more points, N1000N \le 1000.

Example 1


2 3
10 6




In the first sample case a possible solution is to change both prices to be 33 bytedollars. It can be proven that changing only one price is not sufficient.

Example 2


3 9
2 10 1




In the second sample case a possible solution is to change the first product's price to 1616 bytedollars, thus the average will be 16+10+13=9\frac{16+10+1}{3}=9.

Log in or sign up to be able to send submissions!