404340: GYM101484 A Bath Temperature

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Bath Temperaturetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Lately Teodoro has been working a lot, solving tons of problems. Now he thinks that he needs some well deserved rest and decided to go to a bath house to take a nice relaxing bath.

Teodoro is very demanding and wants the temperature of the water to be exactly X degrees celsius. The bath house has N taps of water, each with a specific water temperature of ai degrees celsius. He can open multiple taps to get the exact temperature that he wants by controlling the proportion of water coming out of each tap.

For example, imagine Teodoro opened two taps: the first tap has water at 50 degrees celsius and the second tap has water at 75 degrees celsius. He opened the taps so that there is four times more water coming out of the first tap than the second tap. The resulting temperature r can be calculated as:

Notice that the resulting temperature will always be a weighted mean of the water temperatures of the open taps.

The amount of money that Teodoro will pay at the bath house depends on how many different taps he opens and Teodoro doesn't have much money to spend, so he wants to know what is the minimum number of taps that he has to open to get the desired temperature.

Input

The first line of the input contains two integers N (1 ≤ N ≤ 105) and X (0 ≤ X ≤ 100), indicating respectively the number of taps and the desired temperature.

The following line contains N integers ai (0 ≤ ai ≤ 100). The i-th integer indicates the temperature of the water that comes out of the i-th tap.

Output

Output the minimum number of taps that Teodoro needs to open to get his desired temperature. Output  - 1 if it is not possible to get the desired temperature in any way.

ExamplesInput
4 50
25 50 75 100
Output
1
Input
2 50
0 100
Output
2

Source/Category

加入题单

上一题 下一题 算法标签: