정수 배열이 주어진다.

서로 다른 두 위치 \(i\), \(j\)를 선택하여 점수를 만들 수 있다.

두 위치를 선택했을 때 얻는 점수는 다음과 같이 정의된다.

\(score(i, j) = digit\_sum(a_i \times a_j)\)

여기서 \(digit\_sum(x)\)는 정수 \(x\)의 각 자릿수의 합을 의미한다.

점수는 단 한 번만 얻을 수 있다. 만들 수 있는 점수 중 최댓값을 구하시오.

입력

첫째 줄에 배열의 길이 \(N\)이 주어진다.

둘째 줄에 배열의 원소 \(a_1, a_2, \ldots, a_N\)이 공백으로 구분되어 주어진다.

출력

만들 수 있는 점수의 최댓값을 출력한다.

제한 사항

• \(2 \le N \le 100,000\)

• \(1 \le a_i \le 999\)

예제 설명 1

선택할 수 있는 두 수는 \(3\)과 \(8\)뿐이다.

\(3 \times 8 = 24\)이고, \(24\)의 자릿수 합은 \(2 + 4 = 6\)이다.

Line 1: \(N\) (\(2 \le N \le 100000\)). Line 2: \(a_1, \dots, a_N\) (\(1 \le a_i \le 999\)).

Print the maximum digit-sum score over all pairs.

riseoj 작성

출처 Online Judge > GoldOJ