Largest Sum of Digit Pairs

You are given a list of N positive integers. For each integer, consider all unordered pairs of its digits. The sum of digit pairs for a number is calculated as follows: if the digits of the number are \(d_1,d_2,\dots,d_k\), then the sum is

[ S = \sum_{1 \le i < j \le k} (d_i + d_j)]

Your task is to find the number which has the largest sum of digit pairs. In the event of a tie (i.e. multiple numbers yielding the same maximum sum), output the smallest number among them.

Note: Each number is processed independently. You will first compute its sum of digit pairs and then determine the answer from the list.

inputFormat

The input is given via standard input and has the following format:

• The first line contains a single integer \(N\), representing the number of numbers.
• The second line contains \(N\) space-separated positive integers.

outputFormat

Output a single integer: the smallest number among those with the largest sum of digit pairs.

4
123 456 789 101112

789