버섯 괴물

Kaylin은 버섯을 좋아한다. 접시에 올려 주면 모두 먹어 치운다! 이 문제에서 Kaylin은 접시에 담긴 버섯을 먹고 있으며, Bartholomew는 접시에 버섯 조각을 더 올려놓는다.

이 문제에서는 10초 간격으로 Kaylin의 접시에 버섯 조각이 몇 개 있는지 살펴본다. Bartholomew는 언제든지 음이 아닌 정수 개의 버섯 조각을 접시에 놓을 수 있으며, 버섯 조각이 접시에서 사라지는 유일한 방법은 Kaylin이 먹는 것이다.

서로 다른 두 가지 계산 방법을 사용하여 Kaylin이 먹었을 수 있는 버섯의 최소 개수를 구하라.

• Kaylin이 언제든지 원하는 개수의 버섯 조각을 먹을 수 있다고 가정한다.

• 접시를 처음 살펴본 시점부터, 접시에 버섯이 있을 때마다 Kaylin이 일정한 속도로 버섯을 먹는다고 가정한다.

예를 들어, 입력이 10 5 15 5이라면 다음과 같다.

첫 번째 방법에서 Kaylin은 적어도 15개의 버섯 조각을 먹었어야 한다. 먼저 5개를 먹고, 그다음 접시에 10개가 더 놓이며, 이후 다시 10개를 먹는다. 이보다 적은 조각을 먹었을 가능성은 없다.

두 번째 방법에서 Kaylin은 적어도 25개의 버섯 조각을 먹었어야 한다. Kaylin이 초당 적어도 1개의 속도로 버섯을 먹어야 한다는 것을 알 수 있다. 처음에 접시에는 10개의 버섯 조각이 있다. 처음 10초 동안 Kaylin은 10개를 먹고, 접시에 5개가 더 놓인다. 다음 5초 동안 Kaylin은 5개를 먹고, 이후 접시는 5초 동안 빈 상태로 유지되며, 그런 다음 Bartholomew가 접시에 15개를 더 놓는다. 마지막 10초 동안 Kaylin은 10개를 먹는다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

소규모 데이터 세트

시간 제한: 240초. 2 ≤ N ≤ 10. 0 ≤ $m_{i}$ ≤ 100.

대규모 데이터 세트

시간 제한: 480초. 2 ≤ N ≤ 1000. 0 ≤ $m_{i}$ ≤ 10000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N 하나가 포함된 한 줄과, 그 뒤에 공백으로 구분된 N개의 정수 $m_{i}$가 포함된 한 줄로 구성된다. 이 정수들은 처음과 그 이후 10초 간격으로 Kaylin의 접시에 있던 버섯의 개수를 나타낸다.

각 테스트 케이스마다 "Case #x: y z"이 포함된 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작한다. y는 첫 번째 계산 방법을 사용할 때 Kaylin이 먹었을 수 있는 버섯의 최소 개수이고, z는 두 번째 계산 방법을 사용할 때 Kaylin이 먹었을 수 있는 버섯의 최소 개수이다.