문제
나뭇가지 위에 n개의 이슬방울이 있고 각각의 이슬방울은 가지고 있는 물의 양은 m이다.
벌레의 위치를 원점으로 했을 때 이슬방울의 좌표는 x1, x2, ..., xn으로 표시한다.
어느 더운 날이다. 1분이 지나면 이슬방울이 가지고 있는 물이 1만큼 줄어든다.
벌레는 매우 목이 말라 물을 마시러 이동한다.
벌레는 좌표 하나를 이동할 수 있는데 이 때 1분이 걸린다.
만약 이슬방울이 있는 곳에 벌레가 도착하면 벌레는 물을 마실 수 있는데 그 때는 시간을 사용하지 않는다.
이슬방울의 좌표들이 주어졌을 때 벌레가 마실 수 있는 물의 최대 양을 구하는 프로그램을 작성하시오.
입력
입력파일 첫줄에는 정수 n와 m이 주어진다(0 ≤ n ≤ 300, 1 ≤ m ≤ 1,000,000). 그 다음 n개의 줄에는 정수 좌표 x1, x2, ..., xn이 주어진다(-10,000 ≤ x1, x2, ... xn ≤10,000). 이때 i ≠ j이면 xi ≠ xj이다.
출력
출력파일은 하나의 정수를 출력하는데 이것은 벌레가 마실 수 있는 물의 최대 양이다.
예제
3 15
6
-3
1
25
출처
Baltic Olympiad in Informatics 2009
로그인해야 코드를 작성할 수 있어요.