어느 시골에, 쌀의 길이라고 불리는 긴 직선 도로가 있다.

이 길을 따라 R 개의 논들이 있다.

각 논들은 1이상 L 이하의 정수좌표를 갖는다.

논들은 좌표 값이 감소하지 않는 순서로 주어진다.

즉, 0 ≤ i < R에 대해서, 논 i 는 좌표 X[i] 에 있다. 1 ≤ X[0] ≤ ... ≤ X[R-1] ≤ L라고 가정할 수 있다.

여러 개의 논이 하나의 같은 좌표에 있을 수 있음을 주의하라.

논에서 수확한 가능한 가장 많은 쌀들을 저장할 수 있는 하나의 쌀 창고를 세우려고 계획하고 있다.

논의 위치와 같이, 쌀 창고의 위치는 1이상 L 이하의 정수좌표에만 있을 수 있다.

쌀 창고는 논들이 위치하고 있는 장소를 포함하여 어떤 곳에든지 세울 수 있다.

수확의 계절에 각 논들은 정확히 트럭 한대 분량의 쌀만 생산할 수 있다.

쌀들을 창고로 옮기기 위해서 트럭 운전사들을 고용하여야 한다.

트럭 운전사는 한 트럭분량의 쌀을 창고로 옮기는데 단위 거리당 1 바트의 요금을 청구한다.

다르게 말하자면, 논으로부터 쌀을 창고로 옮기는 비용은, 논의 좌표 값과 창고의 좌표 값의 차이와 같다.

불행히도, 올해의 예산이 충분하지 못하여 쌀의 수송에는 최대 B 바트 까지만 사용할 수 있다.

여러분이 해야 할 일은 가능한 가장 많은 쌀을 창고로 모으기 위한 창고의 위치를 결정하는 것이다.

해야 할 일(Your task) 반드시 최적의 쌀 창고의 위치를 찾아야 하고,

예산 범위 이내에서 쌀 창고까지 옮길 수 있는 최대 쌀의 양이 트럭 몇 대 분량 인지를 구하여야 한다.

쌀을 옮기는데 허용된 예산은 매우 클 수가 있음을 주의하라.

예산은 64-비트의 정수로 주어지고, 계산 과정에서는 64-비트의 정수를 사용하도록 권장한다.

예제 설명

다음의 경우를 고려해보자. R=5, L=20, B=6, X= 1 2 10 12 14

이 경우에는 창고의 위치에 대한 여러 개의 최적 위치가 있다:

10 이상 14 이하의 어느 정수 위치에든지 쌀 창고를 둘 수 있다.

위의 그림은 최적 위치들 중의 하나를 보여준다.

이 경우 10 과 12, 14 의 위치에 있는 논으로부터 쌀들을 옮길 수 있다.

어떤 최적의 창고 위치에 대해서든지, 쌀의 총 수송비용은 6 바트 이하이다.

세 개보다 많은 논으로부터 쌀을 모을 수 있는 창고의 위치는 존재하지 않으므로, 3 최적이다.

쌀 창고(Rice Hub) timer 1s memory 256MB

쌀 창고(Rice Hub) 1s 256MB