Taps

Interview

Time limit1sMemory limit128 MB

Summary

Close the fewest flowing taps so the average temperature of the water still flowing reaches at least w.

Level: Easy3 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

An industrial plant has $n$ taps that water can flow from. Each tap has a gauge showing the temperature of the water for that tap. Water flows from a tap only if its set temperature is greater than $0$ . Every tap releases water at the same rate, and all of it collects in one shared reservoir.

Given the temperature of each tap, find the minimum number of taps you must close so that the water temperature in the reservoir is at least $w$ .

Assume the reservoir temperature equals the average temperature of all taps that water is flowing from. The temperature is not affected by the surrounding air.

Input

The first line contains two integers $n$ and $w$ , the number of taps and the target temperature ( $1 \le n \le 10^6$ , $1 \le w \le 100$ ). The second line contains $n$ integers $t_1, t_2, \dots, t_n$ , where $t_i$ is the water temperature set for the $i$ -th tap ( $-100 \le t_i \le 100$ ).

Output

Print a single integer: the minimum number of taps to close so that the reservoir temperature is at least $w$ degrees. If such a temperature cannot be reached, print the single word NIE instead.

Hint

To raise the average with as few closures as possible, close the flowing taps (those with a positive temperature) starting from the lowest temperature.

Examples3

Example 1
Input
```
6 4
2 1 3 5 7 1
```
Expected output
```
2
```
Example 2
Input
```
3 10
5 4 3
```
Expected output
```
NIE
```
Example 3
Input
```
5 1
-3 2 0 1 4
```
Expected output
```
0
```