33684번 - 소스 더하기

문제

한 작은 마을에서 요리 대회가 열렸다. 대회에 참가한 각 요리사에게는 $N$개의 소스가 제공된다. 각 소스에는 1ドル$부터 $N$까지의 번호가 붙어 있으며, $i$번 소스의 맛은 정수 $A_i$이다.

요리사들은 소스를 섞어 새로운 맛을 만들어낼 수 있다. 요리사는 서로 다른 두 소스를 선택하여, 하나의 소스에 다른 소스를 추가하는 방식으로 섞을 수 있다. 이때, 섞인 소스의 맛은 두 소스의 맛을 더한 값이다. 즉, $i$번 소스에 $j$번 소스를 더하는 연산을 다음과 같이 수행할 수 있다. (단, 1ドル \leq i, j \leq N$ 이고 $i \neq j$)

$$A_i := A_i + A_j$$

$j$번 소스는 여러 번 사용될 수 있지만 연산의 영향을 받지 않고 원래의 값을 유지한다. 이는 요리사가 특정 소스의 일부를 덜어내어 다른 소스에 첨가하는 방식으로 섞기 때문이다. 따라서, 한 소스의 맛을 변화시키면서도 다른 소스는 원래의 상태를 유지할 수 있다. 이전에 선택했던 소스도 다시 선택해서 한 번 섞은 소스가 다시 다른 소스와 섞이는 방식으로 계속해서 연산을 반복할 수 있다. 하지만 소스의 맛이 너무 강해지면 요리를 망칠 위험이 있다. 따라서, $N$개의 소스 중에서 맛이 $K$를 초과하는 소스가 하나라도 있다면, 어떠한 소스도 더 이상 섞을 수 없다.

요리사들은 이 대회를 최대한 오래 즐기고 싶어 한다. 그들이 소스를 섞을 수 있는 최대 횟수는 몇 번일까?

입력

첫 번째 줄에 소스의 개수 $N$과 소스 맛의 상한 $K$가 공백으로 구분되어 주어진다. $(2 \le N \le 100,000円;$ 1ドル \le K \le 10^9)$

두 번째 줄에 초기 각 소스의 맛 $A_1,ドル $A_2,ドル $\cdots,ドル $A_N$이 공백으로 구분되어 주어진다. $( -10^9 \leq A_i \leq 10^9 )$

입력으로 주어지는 수는 모두 정수이다.

출력

첫 번째 줄에 요리사들이 소스를 섞을 수 있는 최대 횟수를 출력한다. 무한히 섞을 수 있다면 -1을 출력한다.

제한

힌트