수아의 사탕 바구니
시간 제한1초메모리 제한512 MB
0에서 출발해 시간이 지날수록 사탕이 줄어드는 바구니들을 최적 순서로 방문해 얻을 수 있는 최대 사탕 수를 구하는 문제입니다.
문제
수아는 x축 위의 0번 위치에 있다. x축 위에는 n개의 사탕 바구니가 놓여 있고, 각 바구니에는 처음에 m개의 사탕이 들어 있다. 바구니들의 위치는 x_1, x_2, ..., x_n이다.
시간이 1만큼 지날 때마다 모든 바구니의 사탕은 1개씩 줄어든다. 수아는 사탕 바구니에 도착하면 그 바구니에 남아 있는 사탕을 즉시 모두 먹을 수 있다. x축 위에서 거리 1만큼 이동하는 데에는 시간 1이 걸린다.
수아가 먹을 수 있는 사탕의 최대 개수를 구하시오.
입력
첫째 줄에 n과 m이 주어진다. 다음 n개의 줄에는 각 사탕 바구니의 위치 x_i가 한 줄에 하나씩 주어진다.
- 0 <= n <= 300
- 1 <= m <= 1,000,000
- -10,000 <= x_i <= 10,000
- 바구니의 위치는 모두 서로 다르다.
출력
수아가 먹을 수 있는 사탕의 최대 개수를 출력한다.