점프하는 애벌레

숲에 나무 $N$개가 1번부터 $N$번까지 나란히 서 있다. $i$번 나무의 높이는 $h_i$다. 애벌레는 지금 1번 나무의 밑, 높이 0에 있고 $N$번 나무의 맨 위, 높이 $h_N$까지 올라가려고 한다.

애벌레는 다음 두 동작 중 하나를 할 수 있다.

1. 오르기. $i$번 나무에서 위로 $u_i$만큼 오른다. 나무보다 위로는 갈 수 없으므로 높이 $y$에서 오르면 높이는 $\min(y + u_i, h_i)$가 된다.
2. 점프. 바로 옆 나무, 즉 $i-1$번이나 $i+1$번 나무로 뛴다. 같은 높이로 건너가지만 옆 나무의 맨 위가 지금 높이보다 낮으면 그 낮은 나무의 맨 위에 내려앉는다. 높이 $y$에서 $j$번 나무로 뛰면 높이는 $\min(y, h_j)$가 된다.

두 동작은 각각 정확히 1초가 걸린다. 나무의 맨 위나 밑에 걸려서 이동한 거리가 줄어들어도 1초를 그대로 쓴다.

동작을 한 뒤에는 1초 동안 쉬어야 하고, 쉬는 사이 중력 때문에 지금 있는 $i$번 나무에서 $d_i$만큼 미끄러져 내려간다. 높이 0보다 아래로는 내려가지 않는다. 예외가 하나 있다. 동작을 마친 자리가 지금 있는 나무의 맨 위면 쉬지 않고 곧바로 다음 동작을 한다.

$N$번 나무의 맨 위에 닿는 순간 여행이 끝난다.

나무의 개수와 각 나무의 $h_i$, $u_i$, $d_i$가 주어질 때, 1번 나무의 밑에서 $N$번 나무의 맨 위까지 가는 데 걸리는 가장 짧은 시간을 초 단위로 구해라.

나무가 8개이고 높이가 왼쪽부터 5, 5, 3, 3, 3, 4, 5, 5이며 모든 $u_i$가 3, 모든 $d_i$가 2인 경우를 보자. 1번 나무의 밑에서 세 번 오르고 그 사이에 두 번 쉬면 5초에 1번 나무의 맨 위에 닿는다. 맨 위이므로 쉬지 않고 6초부터 9초까지 2, 3, 4, 5번 나무로 차례로 뛰는데 매번 그 나무의 맨 위에 내려앉으므로 한 번도 쉬지 않는다. 10초에 6번 나무로 뛰면 높이 3에 서지만 6번 나무의 맨 위는 4이므로 11초에 쉬면서 높이 1로 미끄러진다. 12초에 올라 6번 나무의 맨 위에 닿고, 13초에 7번 나무로 뛰어 높이 4에 서고, 14초에 쉬면서 높이 2가 되고, 15초에 올라 7번 나무의 맨 위 5에 닿고, 16초에 8번 나무로 뛰면 높이 5가 8번 나무의 맨 위여서 여행이 끝난다. 이 경로는 16초가 걸리지만 가장 빠른 경로는 아니다. 여덟 나무의 밑을 따라 계속 뛰어 8번 나무까지 간 다음 마지막 나무만 오르는 경로는 19초가 걸린다. 밑에서 뛰면 내려앉은 자리가 맨 위가 아니므로 매번 쉬어야 하고, 높이 0에서는 쉬는 동안 더 미끄러지지 않는다.

첫 줄에 테스트 케이스의 개수 $K$가 주어진다. ($1 \le K \le 10$)

각 테스트 케이스는 네 줄이다.

1. 첫 줄에 나무의 개수 $N$이 주어진다. ($1 \le N \le 1000$)
2. 둘째 줄에 $h_1, h_2, \dots, h_N$이 주어진다. $h_i$는 $i$번 나무의 높이다. ($1 \le h_i \le 1000$)
3. 셋째 줄에 $u_1, u_2, \dots, u_N$이 주어진다. $u_i$는 $i$번 나무에서 한 번에 오르는 높이다. ($1 \le u_i \le 1000$)
4. 넷째 줄에 $d_1, d_2, \dots, d_N$이 주어진다. $d_i$는 $i$번 나무에서 1초 쉬는 동안 미끄러져 내려가는 높이다. ($0 \le d_i \le 1000$)

각 테스트 케이스마다 애벌레가 $N$번 나무의 맨 위에 닿는 데 걸리는 가장 짧은 시간을 초 단위로 한 줄에 출력한다. 닿을 수 없으면 대문자로 NEVER를 출력한다.