Tuenti Challenge 7

Challenge 4 - Help Pythagoras Junior

triangles

Pythagoras Junior is not a great mathematician like his great great great grandfather. When he gets a list of numbers, he finds it hard to match 3 numbers and create a triangle out of them.

You need to help Pythagoras Junior to identify which is the smallest possible triangle given a list of side lengths. We define the smallest triangle as the one with the minimum perimeter.

Input

The first line will contain an integer C, the number of cases for our problem.
Each case consists of a line starting with an integer N, the number of sides, followed by N integers, each indicating the length of a side. All the integers are separated by spaces.

Output

For each case, a line starting with "Case #x: " followed by the perimeter of the smallest triangle or, if it's not possible to form a valid triangle, "IMPOSSIBLE". Every line is followed by a new line character.

Examples

Case 1:

6 13 9 1 13 17 6

Case 2:

7 110 40 10 1 20 60 3

In Case 1, the answer is 27, as the triangle with the smallest perimeter is (13, 13, 1).
In Case 2, the answer is IMPOSSIBLE. You cannot create a valid triangle from any three of the given numbers.

Limits

  • 3 ≤ N ≤ 105
  • 1 ≤ Lengths ≤ 232

Sample Input

2
6 13 9 1 13 17 6
7 110 40 10 1 20 60 3

Sample Output

Case #1: 27
Case #2: IMPOSSIBLE

Test your code

You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want to. Be careful with extra whitespaces, the output should be exactly as described.

Test your program against the input provided in the test phase

Download test input

Program output:

Test your program against the input provided in the submit phase

Download input

Program output:

During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.

In the actual contest you first need to solve the test phase before submitting the code, you must provide the source code used to solve the challenge and you can only submit once (once your solution is submitted you won't be able to amend it to fix issues or make it faster).

If you have any doubts, please check the info section.