시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 150 94 82 64.567%

문제

마나 수정 M개가 신 나무스트럼에 떨어졌다. 마나 수정이 떨어진 후 되살아난 시체들로부터 마을을 지켜야 한다. 마을의 수장 Marko는 전투를 통해 되살아난 시체들을 만든 마법사 Kul’den을 생포하는 데 성공했다. Kul’den을 심문한 결과 M개의 마나 수정이 되살아난 시체에게 마나 공급을 하고 있으며, 이것들을 모두 파괴하면 되살아난 시체들이 멈춘다는 사실을 알아내었다. Marko는 마을에 있는 둔 망치를 사용해 마나 수정을 모두 파괴하기로 했다. 둔 망치는 한 번에 하나의 마나 수정에만 힘을 가할 수 있다.

Marko가 둔 망치를 이용해 마나 수정을 하나씩 파괴하던 도중, 큰 폭발이 일어났다. 이 폭발로 묶인 채로 마나 수정의 파괴를 옆에서 지켜보던 Kul’den은 부상을 입었지만, 되살아난 시체를 불러온 당사자를 치료해줄 마을 사람은 없었다.

마을의 대 마법사 매디브는 폭발의 원인을 분석했고, 그 결과 신 나무스트럼 마을에 떨어진 M개의 마나 수정 중 일부에 큰 마나가 응집되어 있는 것을 알게 되었다. 이러한 마나 수정을 파괴할 수 있는 최소 힘에 비해 너무 강한 힘으로 파괴하면, 마나 수정 속의 응집되어 있던 마나가 과부하를 일으켜 큰 폭발이 일어나게 된다.

하지만 매디브는 어떤 마나 수정에 큰 마나가 응집되어 있는지 판별할 능력이 없었다. 고민 끝에, 마을의 샤먼 타사다르를 찾아갔다. 타사다르가 남아있는 마나 수정들을 감정한 결과, 남은 마나 수정 중 단 하나만이 큰 마나가 응집되어 있다는 것을 파악할 수 있었다. 즉, 남아있는 마나 수정들 중 단 하나의 마나 수정만이 파괴 시 폭발할 가능성이 있다는 뜻이다. 하지만 폭발할 가능성이 있는 마나 수정이라도 이를 적당한 힘으로 파괴한다면(필요한 힘보다 월등히 강력한 힘으로 파괴하지 않는다면) 폭발 없이 파괴할 수 있을 것이다.

타사다르는 남은 N개의 마나 수정들 중 어떤 것에 마나가 응집되어 있는지 판별하기 위해, 각 마나 수정의 무게와 부피, 표면적을 측정했다. 이 값과 비수사의 고서에 기록된 방식을 이용해 폭발 가능성이 있는 마나 수정을 판별해냈지만, 여전히 이 마나 수정에 어느 정도의 힘을 가해야 폭발 없이 파괴할 수 있는지는 모른다.

각 마나 수정의 강도는 무게를 부피로 나눈 값에 비례한다. 하지만 어떻게 비례하는지는 모르기 때문에, 정확한 값은 파악할 수 없다. 대신 두 마나 수정이 있으면 어떤 수정이 더 강도가 높은 지 비교하는 방법은 있다. 이를 통해 모든 마나 수정 쌍을 최대한 비교한 결과, N개의 마나 수정은 모두 서로 다른 강도를 가지고 있다는 사실을 파악했고, 마나가 응집되어 있는 마나 수정은 남은 N개의 마나 수정 중에 K번째로 강한 강도를 가지고 있다는 것을 알아냈다. 즉, 마나가 응집되어 있어 폭발 가능성이 있는 마나 수정보다 (K-1)개의 마나 수정이 더 강한 강도를 가지고 있고, (N-K)개의 마나 수정이 더 약한 강도를 가지고 있다는 뜻이다. 또한, 각각의 마나 수정들 사이의 강도 순서가 어떤 지도 이미 알고 있다!

둔 망치로 마나 수정을 내리치는 힘을 정교하게 조정하기 위해, 마을에서 가장 망치를 잘 다루는 마을의 대장장이 린드홀에게 둔 망치를 이용해 마나 수정을 파괴하도록 하려고 한다. 마을의 대장장이 린드홀은 둔 망치를 내리칠 때 이를 P이하의 힘으로 내리칠 수 있다. 린드홀은 망치를 매우 잘 다루기 때문에, 마음속으로 P이하의 양의 실수 p를 상상하며 힘을 조절해 망치를 내리칠 경우, 마나 수정에 정확히 p의 힘을 가할 수 있다. 린드홀의 힘과 둔 망치는 마나 수정을 파괴하기에 충분히 강력하므로 최대 파워인 P의 힘으로 내리치면 어떤 마나 수정이던 한 번에 파괴할 수 있다. (하지만 이렇게 마나가 응집된 마나 수정을 한 번에 파괴한다면, 필요 이상의 큰 힘을 가하게 되어 마나 수정이 폭발할지도 모른다!)

각 N개의 마나 수정의 강도는 N개의 서로 다른 양의 실수로 표현될 수 있는데, 모든 강도는 P이하임이 보장된다. 마나 수정의 강도가 X인 경우, X이상의 힘으로 둔 망치를 내리치면 마나 수정은 파괴되어 사라진다.(사라진 마나 수정에는 더 이상 망치를 내리칠 수 없다!) 반면 X미만의 힘으로 내리치면 아무런 변화가 없다. 응집된 마나 수정은 그 강도 보다 W이상 강한 힘으로 내리치면, 응집된 마나가 과부하를 일으켜 큰 폭발이 일어나게 된다. 이러한 폭발이 일어날 수 있는 경우는 무조건 피하려고 한다.

각 마나 수정의 강도 순서는 알고 있지만, 실제 강도는 알지 못한다. 하지만 우리는 최악의 경우를 대비하려고 한다. 마나가 응집된 마나 수정은 굉장히 위험하기 때문에, 최대한 빠르게 파괴하고 싶다. 당신의 임무는 린드홀에게 몇 번째로 강한 강도의 마나 수정을 얼마만큼의 힘으로 내리칠지 명령하여, 최악의 경우에 망치를 내리치는 횟수를 최소화하는 전략을 사용하고자 한다. 이러한 전략을 사용 했을 때 최악의 경우 망치를 내리쳐야 하는 횟수를 구하여라. (폭발할 가능성이 조금이라도 있는 명령을 내린다면, 린드홀은 둔 망치를 휘둘러 당신의 명치를 파괴할 것이다. 이러한 경우는 피해야 한다.)

입력

첫 번째 줄에 네 개의 정수 N, K, P, W가 주어진다. 이는 순서대로 남아있는 마나 수정의 수 N(1 ≤ N ≤ 1,000)과 마나가 응집된 마나 수정의 강도 순위를 나타내는 K(1 ≤ K ≤ N), 둔 망치의 최대 파워 P(1 ≤ P ≤ 2,000), 폭발 위험이 있는 힘 차이 W(1 ≤ W ≤ P)를 의미한다. 각 마나 수정의 강도를 표현 불가능한 경우는 주어지지 않는다.

출력

최악의 경우 마나가 응집된 마나 수정을 파괴하기까지 내리치는 횟수를 최소화하는 전략을 사용했을 때, 마나가 응집된 마나 수정을 파괴하기까지 망치를 내리치는 최대 횟수를 출력한다.

예제 입력

2 1 90 25

예제 출력

4

힌트