Kaylin rất thích nấm. Chỉ cần đặt chúng lên đĩa là cô ấy sẽ ăn hết! Trong bài này, cô ấy đang ăn nấm trên một chiếc đĩa, còn Bartholomew thì đặt thêm các miếng nấm lên đĩa.

Ta quan sát số miếng nấm trên đĩa ở các thời điểm cách nhau 10 giây. Bartholomew có thể đặt thêm một số nguyên không âm miếng nấm vào bất kỳ lúc nào; cách duy nhất để nấm rời khỏi đĩa là bị ăn.

Hãy tính số nấm ít nhất mà Kaylin có thể đã ăn theo hai phương pháp tính khác nhau:

1. Giả sử Kaylin có thể ăn bất kỳ số miếng nấm nào vào bất kỳ lúc nào.
2. Giả sử rằng, kể từ lần đầu tiên ta nhìn vào đĩa, Kaylin ăn nấm với tốc độ không đổi bất cứ khi nào trên đĩa còn nấm.

Ví dụ, nếu dữ liệu là 10 5 15 5:

Theo phương pháp thứ nhất, Kaylin phải ăn ít nhất 15 miếng nấm: đầu tiên cô ăn 5 miếng, sau đó 10 miếng nữa được đặt lên đĩa, rồi cô ăn thêm 10 miếng. Không có cách nào để cô ăn ít hơn.

Theo phương pháp thứ hai, Kaylin phải ăn ít nhất 25 miếng. Ta xác định được rằng tốc độ ăn phải ít nhất là 1 miếng mỗi giây. Ban đầu cô có 10 miếng trên đĩa. Trong 10 giây đầu, cô ăn 10 miếng và 5 miếng nữa được đặt lên đĩa. Trong 5 giây tiếp theo, cô ăn 5 miếng; đĩa rỗng trong 5 giây còn lại, rồi Bartholomew đặt thêm 15 miếng. Cuối cùng, cô ăn 10 miếng trong 10 giây cuối.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa số nguyên \(N\), tiếp theo là một dòng chứa \(N\) số nguyên \(m_i\) cách nhau bởi dấu cách: số nấm trên đĩa của Kaylin lúc bắt đầu và tại các thời điểm cách nhau 10 giây.

Dữ liệu ra

Với mỗi bộ test, in một dòng dạng Case #x: y z, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), \(y\) là số nấm ít nhất Kaylin có thể đã ăn theo phương pháp thứ nhất và \(z\) là số nấm ít nhất theo phương pháp thứ hai.

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

• Nhỏ: \(2 \le N \le 10\); \(0 \le m_i \le 100\).
• Lớn: \(2 \le N \le 1000\); \(0 \le m_i \le 10000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
4
10 5 15 5
2
100 100
8
81 81 81 81 81 81 81 0
6
23 90 40 0 100 9

Case #1: 15 25
Case #2: 0 0
Case #3: 81 567
Case #4: 181 244

Nguồn

Google Code Jam 2015, Vòng 1A, bài Mushroom Monster.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.