gamewithnumber

Chúng tôi có một trò chơi để bạn chơi với máy tính (Com). Mục tiêu của bạn là chọn số từ một mảng có độ dài chẵn để đạt điểm tối đa theo các quy tắc sau:

· Lượt đầu tiên là bạn, sau đó đến lượt máy tính, v.v.        

· Mỗi lượt, bạn chỉ có thể chọn một số ở bên trái hoặc bên phải trong mảng hiện có.        

· Khi một phần tử được chọn, nó sẽ bị xóa khỏi mảng.        

Trò chơi có hai cấp độ, cấp độ đầu tiên rất dễ - máy tính rất ngu ngốc, và cấp độ thứ hai rất khó - máy tính rất thông minh, vậy thì điểm tối đa bạn có thể đạt được trong hai trường hợp có thể khác nhau.

Các giá trị là gì?

Ví dụ, nếu trò chơi có 4 số như bên dưới

5            8            4            2

Ở cấp độ rất dễ , số điểm tối đa bạn có thể đạt được là 13:

Lượt 1: Bạn chọn 5,

Lượt 2: Com   pick 2,

Lượt thứ 3: Bạn chọn 8,

Lượt cuối: Chọn Com 4.

Trong trường hợp cấp độ rất khó , số điểm tối đa bạn có thể đạt được chỉ là 10:

Lượt 1: Bạn chọn 2,

Lượt 2: Com   pick 5,

Lượt thứ 3: Bạn chọn 8,

Lượt cuối: Chọn Com 4.

 

Lưu ý rằng: nếu bạn chọn 5 trước, thì máy tính thông minh sẽ chọn 8, vì vậy bạn chỉ có thể chọn 9.

 

Do đó, đáp án cho trường hợp này là 13 10.

 

Giới hạn thời gian: 10 giây (C/C++), 20 giây (Java).

Giới hạn gửi:  10 lần.

 

[Đầu vào]

Dòng đầu tiên là T (T ≤ 50), số lượng các test.
Mỗi test được đưa ra trên hai   dòng, dòng đầu tiên là số N (N <= 30), N là số chẵn , dòng tiếp theo là các phần tử của mảng, mỗi phần tử lớn hơn 0 và nhỏ hơn hoặc bằng 1000.

[Đầu ra]

In ra câu trả lời cho mỗi trường hợp kiểm tra trên 2 dòng, dòng đầu tiên là "Trường hợp số x" , trong đó x là số trường hợp kiểm tra.

Dòng tiếp theo là hai số, số đầu tiên là số điểm tối đa bạn có thể đạt được ở cấp độ rất dễ và số tiếp theo là số điểm tối đa bạn có thể đạt được ở cấp độ rất khó.

 

[Vật mẫu]

Đầu vào:

5

4

5 8 4 2

4

8 5 4 2 

.............

 

Đầu ra:

Trường hợp 1

13 10

Trường hợp số 2

13 12

Trường hợp số 3

192 181

Trường hợp số 4

809 606

Trường hợp số 5

6175 4557