팬케이크 모으기

Alice와 Bob은 둘 다 단것을 좋아하며, 팬케이크를 모으는 게임을 하려고 한다. 테이블 위에는 $\mathbf{N}$개의 팬케이크 더미가 일렬로 놓여 있고, $1$부터 $\mathbf{N}$까지의 번호가 붙어 있다. $i$번째 더미에는 정확히 $\mathbf{A_i}$개의 팬케이크가 있다. Alice와 Bob은 번갈아 차례를 진행하며 더미 전체를 차지하여 팬케이크를 모은다. 첫 번째 차례에 Alice는 번호가 $\mathbf{L_a}$ 이상 $\mathbf{R_a}$ 이하인 더미 하나를 골라 차지해야 한다. 그다음 Bob은 번호가 $\mathbf{L_b}$ 이상 $\mathbf{R_b}$ 이하이면서 Alice가 고른 것과 다른 더미 하나를 골라 차지해야 한다.

이후의 차례마다 두 사람은 각자 자신이 이전에 차지한 더미와 인접한, 아직 차지되지 않은 더미 하나를 골라야 한다. 즉, Alice가 첫 번째 차례가 아닌 자신의 어느 차례에 더미 $i$을 차지하려면, 이전의 어느 차례에 더미 $i-1$ 또는 더미 $i+1$을 차지했어야 한다. Bob에게도 마찬가지이다. 어느 시점에 한 플레이어가 고를 수 있는 유효한 더미가 없다면, 그 플레이어는 해당 차례를 건너뛰고 아무 더미도 차지하지 않는다.

모든 더미의 주인이 정해지면 게임이 끝난다. 이때 Alice는 자신이 차지한 모든 더미의 팬케이크를 전부 가져가고, Bob은 자신이 차지한 모든 더미의 팬케이크를 전부 가져간다.

Alice는 자신이 가능한 한 많은 팬케이크를 얻고 싶어 하고, Bob도 자신이 가능한 한 많은 팬케이크를 얻고 싶어 한다. 두 사람 모두 최적으로 플레이할 때 Alice가 모을 수 있는 팬케이크 수의 최댓값을 구하도록 도와주자.

제한

시간 제한: 30초. 메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{A_i} \le 10^9$. $1 \le \mathbf{L_a} \le \mathbf{R_a} \le \mathbf{N}$ $1 \le \mathbf{L_b} \le \mathbf{R_b} \le \mathbf{N}$ $\mathbf{L_a} \le \mathbf{L_b} = \mathbf{R_b} \le \mathbf{R_a}$인 경우는 없다. (Alice가 무엇을 고르든 Bob은 첫 번째 차례에 더미 하나를 고를 수 있음이 보장된다.)

테스트 세트 1 (결과 공개)

$2 \le \mathbf{N} \le 100$.

테스트 세트 2 (결과 공개)

$2 \le \mathbf{N} \le 10^5$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다.

각 테스트 케이스의 첫 번째 줄에는 팬케이크 더미의 수를 나타내는 정수 $\mathbf{N}$이 주어진다.

두 번째 줄에는 $\mathbf{N}$개의 정수 $\mathbf{A_1}, \mathbf{A_2}, \dots, \mathbf{A_N}$가 주어지며, 여기서 $\mathbf{A_i}$는 더미 $i$에 있는 팬케이크의 수를 나타낸다.

세 번째 줄에는 $4$개의 정수 $\mathbf{L_a}$, $\mathbf{R_a}$, $\mathbf{L_b}$, $\mathbf{R_b}$가 주어진다. 이들은 각각 Alice와 Bob이 첫 번째 차례에 고를 수 있는 팬케이크 더미 번호의 양 끝을 포함하는 범위를 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 게임에서 최적으로 플레이했을 때 Alice가 모을 수 있는 팬케이크 수의 최댓값이다.

예제 케이스 #1에는 $30, 50, 40, 20, 10$개의 팬케이크가 담긴 팬케이크 더미가 $5$개 있다. 게임을 시작할 때 Alice는 첫 번째 또는 두 번째 더미를 고를 수 있고, Bob은 네 번째 또는 다섯 번째 더미를 고를 수 있다. 두 사람 모두 최적으로 플레이하는 한 가지 방법은 다음과 같다.

• 처음에 Alice가 더미 $2$을 차지하고, 이어서 Bob이 더미 $4$을 차지한다.

• Alice가 자신의 두 번째 차례에 더미 $3$을 차지하고, 이어서 Bob이 자신의 두 번째 차례에 더미 $5$을 차지한다.

• Alice가 자신의 세 번째 차례에 더미 $1$을 차지하고, 모든 더미의 주인이 정해졌으므로 게임이 끝난다.

게임이 끝났을 때 Alice는 더미 $1, 2$, 그리고 $3$을 차지했고, Bob은 더미 $4$과 $5$을 차지했다. Alice가 모으는 팬케이크의 수는 $30+50+40=120$이다.

예제 케이스 #2에서 최적으로 플레이하는 한 가지 방법은 다음과 같다.

• 처음에 Alice가 더미 $3$을 차지하고, 이어서 Bob이 더미 $2$을 차지한다.

• Alice가 자신의 두 번째 차례에 더미 $4$을 차지하고, 이어서 Bob이 자신의 두 번째 차례에 더미 $1$을 차지한다.

• Alice가 자신의 세 번째 차례에 더미 $5$을 차지하고, 모든 더미의 주인이 정해졌으므로 게임이 끝난다.

Alice가 모으는 팬케이크의 수는 $80+10+10=100$이다.

예제 케이스 #3에서 두 사람 모두 첫 번째 차례에 아무 더미나 차지할 수 있다. 더미 $1$은 나머지를 모두 합친 것보다 가치가 크므로, Alice는 Bob보다 먼저 그 더미를 차지한다. 그러면 Bob은 더미 $2$을 차지하여 Alice가 이후의 모든 차례를 건너뛰게 만들 수 있다. 그래도 게임이 끝났을 때 Alice는 $90$개의 팬케이크를, Bob은 겨우 $30$개의 팬케이크를 가진다.