격자 도로의 속도

문제

남북 방향 도로가 동서 방향 도로 위로 고가로 지나가는 격자형 도시를 생각하자. 같은 방향의 이웃한 두 도로는 일정한 거리(마일)만큼 떨어져 있다. 모든 도로는 양방향 통행이며, 모든 교차로에는 진입·진출 램프가 있어 남북 도로와 동서 도로 사이를 갈아타는 데 걸리는 시간은 없다. 신호등이 없고 교통량도 거의 없다.

각 도로에는 고유한 제한 속도가 있으며, 한 도로의 제한 속도는 도로 전체에서, 그리고 양방향 모두 같다. 교차로는 열 번호와 행 번호로 나타낸다. 남서쪽 모서리가 $(1, 1)$이고, $n \times n$ 격자에서 남동쪽 모서리는 $(n, 1)$이다.

연비는 속도에 따라 달라진다. 자동차의 속도는 항상 양의 정수인 $5$의 배수(mph, 시속 마일)이다. 속도가 $v$ mph인 자동차의 연비는 $80 - 0.03,v^2$ mpg(갤런당 마일)이다.

교차로 $(x_s, y_s)$에서 교차로 $(x_t, y_t)$까지 한 번 이동할 때, 다음을 모두 만족하도록 각 구간의 속도를 정해야 한다.

자동차는 인접한 두 교차로 사이에서 속도를 바꾸지 않는다(속도는 교차로에서만 바꿀 수 있다).
자동차는 현재 달리는 도로의 제한 속도를 넘지 않는다.
자동차는 출발지와 도착지 사이를 가능한 한 짧은 거리로 이동한다(즉, 목적지에서 멀어지는 방향으로는 이동하지 않는다).
자동차는 허용된 시간 구간 안에 도착한다.

각 이동에 대해 가장 빨리 도착하는 방법과 연료를 가장 적게 쓰는 방법을 모두 구하여라.

입력

첫째 줄에 시나리오의 수 $t$가 주어진다.

각 시나리오는 다섯 줄로 이루어진다.

정수 $n$ ($n \le 10$). 동서 방향 도로의 수이자 남북 방향 도로의 수이다.
정수 $g$ ($g < 100$). 같은 방향 이웃 도로 사이의 간격(마일)이다.
$n$개의 정수. 동서(가로) 도로의 제한 속도이며, $1$행부터 $n$행까지의 순서이다.
$n$개의 정수. 남북(세로) 도로의 제한 속도이며, $1$열부터 $n$열까지의 순서이다.
여섯 개의 정수 $x_s\ y_s\ x_t\ y_t\ a\ b$. 출발 교차로의 열·행, 도착 교차로의 열·행, 그리고 허용되는 최소·최대 이동 시간 $a \le b$(분, 양 끝 포함)이다.

가장 큰 제한 속도는 $50$이다. $a$와 $b$는 모두 $1000$ 이하이다.

출력

각 시나리오마다 먼저 다음 줄을 출력한다.

Scenario k:

여기서 $k$는 $1$부터 시작하는 시나리오 번호이다.

허용된 시간 구간 안에 이동을 마칠 수 없으면 다음 한 줄만 출력한다.

IMPOSSIBLE

그렇지 않으면 두 줄을 더 출력한다. 둘째 줄에는 허용 구간 안에서 가장 빠른 도착 시간과, 그 시간에 도착할 때 필요한 최소 연료를 출력한다.

The earliest  arrival: T minutes, fuel F gallons

셋째 줄에는 허용 구간 안에서 쓸 수 있는 최소 연료와, 그만큼의 연료로 도착할 수 있는 가장 빠른 시간을 출력한다.

The economical travel: T minutes, fuel F gallons

모든 도착 시간 $T$는 분 단위 정수이며 올림한 값이다. 모든 연료량 $F$는 소수점 아래 둘째 자리까지 출력한다. 위 형식의 공백과 문장 부호를 정확히 지켜야 한다(earliest 뒤의 공백 두 칸에 유의).