Triangles

Time limit1sMemory limit128 MB

Summary

Given a list of segment lengths, find the largest perimeter of a non-degenerate triangle formed by three of them, or print NIE if none exists.

Level: Medium4 of 10
Topics: Sorting, Greedy
Solved: No attempts yet

Problem

You are given a finite sequence of positive integers, each at most one billion, where every number is the length of a line segment. Three segments can form a (non-degenerate) triangle exactly when the sum of the two shorter lengths is strictly greater than the longest length.

Consider every way to pick three of the given segments that can form a triangle. Output the largest possible perimeter (the sum of the three chosen lengths) over all such triangles. If no three segments can form a triangle, output NIE.

Input

The input contains a finite sequence of at least three positive integers, each not greater than 1,000,000,000, followed by the number 0. Each number is on its own line. The positive numbers are the segment lengths, and 0 marks the end of the data. The input is always well-formed, so your program does not need to validate it.

Output

Print a single line. If three of the given segments can form a triangle, print the maximum possible perimeter of such a triangle. Otherwise, print the single word NIE.

Examples2

Example 1
Input
```
250
1
105
150
325
99999
73
0
```
Expected output
```
725
```
Example 2
Input
```
105
325
55
12555
1700
0
```
Expected output
```
NIE
```