문제 설명
세종이는 다양한 크기와 색을 갖는 보석들을 운반하고 있다. 보석들의 크기는 1부터 m까지의 자연수이고, 총 n개의 보석들이 작업대 위에 일렬로 놓여있다.
세종이는 여러 개의 보석들을 한 번에 집을 수 있는 커다란 집게를 가지고 있다. 이 집게는 균형값(k)이라는 것이 있는데, 집게로 집어내는 보석들의 최대 크기와 최소 크기의 차이가 균형값보다 작거나 같아야 안정적으로 보석들을 집어 올릴 수 있다.
예를 들어 작업대 위에 놓인 보석의 크기가 순서대로 2 3 2 4 5 3 4 3 4 5 6 3 6 일 때, 균형값이 2인 집게를 이용할 때는 한 번에 총 7개까지의 보석을 집을 수 있다.
(다음 그림과 같이 최댓 크기와 최소 크기의 차이가 2인 4 5 3 4 3 4 5의 보석을 집을 수 있다.)
작업대 위에 일렬로 놓인 보석들의 크기가 주어질 때 집게를 이용하여 집어낼 수 있는 보석들의 최대 개수를 구하는 프로그램을 작성하시오.
세종이는 여러 개의 보석들을 한 번에 집을 수 있는 커다란 집게를 가지고 있다. 이 집게는 균형값(k)이라는 것이 있는데, 집게로 집어내는 보석들의 최대 크기와 최소 크기의 차이가 균형값보다 작거나 같아야 안정적으로 보석들을 집어 올릴 수 있다.
예를 들어 작업대 위에 놓인 보석의 크기가 순서대로 2 3 2 4 5 3 4 3 4 5 6 3 6 일 때, 균형값이 2인 집게를 이용할 때는 한 번에 총 7개까지의 보석을 집을 수 있다.
(다음 그림과 같이 최댓 크기와 최소 크기의 차이가 2인 4 5 3 4 3 4 5의 보석을 집을 수 있다.)
작업대 위에 일렬로 놓인 보석들의 크기가 주어질 때 집게를 이용하여 집어낼 수 있는 보석들의 최대 개수를 구하는 프로그램을 작성하시오.
입력 설명
첫 번재 줄에는 n, m, k가 공백으로 구분되어 입력된다.
\((1 \le n, m, k\le 100,000)\)
\((1 \le n, m, k\le 100,000)\)
출력 설명
균형값 k인 집게로 집을 수 있는 보석의 최대 개수를 출력한다.
입력 예시 Copy
13 6 2
2 3 2 4 5 3 4 3 3 5 6 3 6
출력 예시 Copy
7