Untitled

BanBongBay
Cho N quả bóng bay với mỗi quả bóng bay có 1 giá trị số.
Người chơi được yêu cầu bắn vỡ các quả bóng bay để có được số điểm lớn nhất.

Điểm của người chơi sẽ được tính bằng tổng các lần bắn bóng bay.
Điểm của mỗi lần bắn bóng bay sẽ bằng tích của 2 quả bóng bay bên cạnh.

Nếu bên cạnh chỉ có 1 quả bóng bay thì điểm sẽ bằng điểm của quả bóng bay này.

Nếu không còn quả bóng bay nào bên cạnh thì điểm sẽ bằng điểm của quả bóng bay vừa bị bắn.



Hãy tìm điểm số lớn nhất và in ra.
N <=10

Điểm của các quả bóng <10000

Định dạng in ra như bên dưới.

input:

5
6
24 41 22 97 39 41
5
84 39 33 59 81
6
99 84 56 68 76 99
8
89 32 42 44 83 38 24 67
8
27 92 81 90 74 88 53 90

Ouput:
Case #1
11348
Case #2
14700
Case #3
30759
Case #4
29289
Case #5
43110

input
50
6
24 41 22 97 39 41
5
84 39 33 59 81
6
99 84 56 68 76 99
8
89 32 42 44 83 38 24 67
8
27 92 81 90 74 88 53 90
9
81 98 69 49 36 19 56 43 33
5
49 65 28 13 32
9
55 97 46 10 12 13 28 12 94
10
1 1 80 90 1 1 80 80 1 1
10
88 77 1 1 99 77 1 1 77 66
9
90 70 30 93 86 92 17 29 59
9
49 26 22 17 74 65 10 55 60
9
99 31 28 79 82 77 95 86 19
9
10 64 42 100 42 32 81 17 68
10
1 10 19 56 90 75 42 92 24 1
10
84 88 44 29 85 43 27 67 32 71
10
63 37 18 82 71 32 15 56 74 98
10
47 29 94 43 45 82 88 30 21 78
10
38 28 88 54 45 79 86 45 14 79
10
62 46 30 93 27 46 69 59 16 77
7
65 24 39 18 10 70 83
7
44 91 39 84 78 95 90
9
27 64 98 25 93 11 82 93 41
6
33 46 31 87 70 45
5
29 88 94 44 74
9
16 64 51 16 44 31 75 28 24
8
48 24 57 93 96 86 87 100
9
39 45 49 50 41 84 61 49 64
7
56 46 12 24 47 62 54
8
85 29 45 73 39 76 43 11
8
18 13 37 83 74 32 96 30
7
22 56 81 94 92 29 81
6
75 31 35 29 53 22
6
89 13 66 15 53 42
5
77 73 94 18 40
5
63 89 91 24 23
9
66 88 72 21 98 72 58 20 98
6
46 59 19 53 95 20
6
57 15 34 69 26 39
6
95 56 45 14 71 10
6
32 30 17 97 24 55
9
85 95 83 95 100 93 72 65 18
10
99 99 99 99 99 99 99 99 99 99
10
1 1 1 1 1 1 1 1 1 1
10
88 88 88 88 88 88 88 88 88 88
10
99 99 99 99 99 1 1 1 1 1 
10
1 1 1 88 88 88 88 1 1 1
10
88 88 1 1 1 1 1 1 99 99
10
1 55 1 55 1 55 1 55 1 55
10
55 1 55 1 55 1 55 1 55 1