cho.sh

프라우드 펭귄

아직 제출이 없습니다시간 제한3초메모리 제한256 MB

문제

프라우드 펭귄(PP)은 도시에서 손꼽히는 관람 시설이다. 북극권 동물을 전문으로 다루어 물고기, 물범, 고래, 그리고 펭귄을 볼 수 있다. 펭귄관이 크게 인기를 끌자 PP는 펭귄이 놀 수 있는 구역을 새로 짓기로 했다.

새 구역은 길고 좁은 트랙이다. 오르막과 내리막이 이어지고 양쪽 끝이 가장 높아서 이동은 언제나 내리막으로 시작한다. 펭귄은 한쪽 끝으로 들어가 걷고 헤엄치고 미끄러지며 반대쪽 끝으로 간다.

계획 단계에 남은 문제는 물을 어떻게 나누어 붓느냐다. 펭귄이 게으른 탓에 PP는 가장 높은 오르막을 최대한 낮추는 쪽을 택했다. 동시에 이사회는 유지비를 줄이려고 쓸 수 있는 물의 양에 상한을 두었다.

일정한 간격으로 잰 트랙의 높이와 쓸 수 있는 물의 양이 주어질 때, 펭귄이 넘어야 하는 가장 높은 오르막을 어디까지 낮출 수 있는지 구하여라.

그림 1: 오르막의 높이를 재는 방법

트랙과 물

트랙의 단면은 점 (0,a0),(1,a1),…,(N,aN)(0, a_0), (1, a_1), \dots, (N, a_N)을 차례로 이은 꺾은선이다. 트랙의 폭은 1이고 이웃한 두 지점 사이는 직선이다.

물은 낮은 쪽으로 흐르므로 웅덩이 하나의 수면은 평평하고, 그 수면보다 낮은 지면은 모두 물에 잠긴다. 양 끝의 높이가 100이고 나머지 지점의 높이는 100 이하라서 물이 트랙 밖으로 흘러나가지 않는다. 물의 양은 단면적으로 재고, 모든 웅덩이의 단면적을 합한 값이 WW 이하여야 한다.

오르막

물을 부은 뒤의 표면은 마른 곳에서는 지면이고 잠긴 곳에서는 수면이다. 오르막은 이 표면을 따라가며 높이가 계속 올라가는 극대 구간이고, 오르막의 높이는 끝점의 높이에서 시작점의 높이를 뺀 값이다. 평평한 구간은 오르막을 끊는다. 그래서 오르막은 물가에서 시작할 수 있고, 높이가 같은 두 지점을 잇는 평평한 지면에서도 오르막이 끊긴다. 펭귄은 양쪽 방향으로 지나가므로 왼쪽으로 올라가는 오르막과 오른쪽으로 올라가는 오르막을 모두 센다.

가장 높은 오르막의 높이를 최소로 만들고 그 높이를 출력한다.

입력

첫 줄에 테스트 케이스의 수 TT가 주어진다. 각 테스트 케이스의 첫 줄에는 트랙의 길이 NN과 쓸 수 있는 물의 양 WW가 주어진다. 다음 줄에는 정수 N+1N+1개 a0,a1,…,aNa_0, a_1, \dots, a_N이 주어진다. a0a_0은 왼쪽 끝의 높이, a1a_1은 왼쪽 끝에서 한 칸 떨어진 지점의 높이, aNa_N은 오른쪽 끝의 높이다.

  • 0<T≤1000 < T \le 100
  • 0<N≤10 0000 < N \le 10\,000
  • 0≤W≤1 000 0000 \le W \le 1\,000\,000
  • 0≤ai≤1000 \le a_i \le 100
  • a0=aN=100a_0 = a_N = 100

출력

각 테스트 케이스마다 가장 낮출 수 있는 최대 오르막의 높이를 한 줄에 출력한다. 값은 소수점 아래 넷째 자리까지 반올림해서 쓴다. 모든 테스트 케이스의 정답은 반올림 경계에서 10−510^{-5}보다 멀리 떨어져 있으므로 10−610^{-6} 정확도로 계산하면 충분하다.