트라이애슬론

트라이애슬론(Triathlon)은 라틴어로 3을 뜻하는 tri와 경기를 뜻하는 athlon을 합친 말이다. 한국에서는 트라이애슬론 대신 철인 3종 경기로 알려져 있다.

트라이애슬론에는 여러 종류가 있다. 올림픽 트라이애슬론은 주어진 구간을 수영한 뒤 사이클을 타고, 마지막으로 마라톤을 한다.

알고리즘에도 트라이애슬론이 있다. 처음 알고리즘 트라이애슬론을 고안한 폰 예스이만이 남긴 문서에는 다음 경기 규칙이 적혀 있다.

• 대회는 17시간 동안 진행하며, 문제는 최소 30문제이다.
• 각 문제는 애드혹, 다이나믹 프로그래밍, 그리디 알고리즘 중 최소 하나의 유형을 포함해야 한다.
• 점수 계산은 자유롭게 정해도 되지만, 애드혹 문제 해결의 비중을 높게 잡아야 한다.

2157년 폰 예스이만을 기념하여 알고리즘 트라이애슬론이 처음 개최되었다. 점수는 다음과 같이 계산한다.

• $a$, $d$, $g$는 각각 애드혹, 다이나믹 프로그래밍, 그리디 알고리즘 문제를 해결해 얻은 점수이다.
• 점수는 $a \times (d + g)$로 계산한다.
• $a = (d+g)$인 경우에는 원래 얻을 점수의 두 배로 계산한다.

대회가 끝나고 시상식을 할 차례이다. 우승자를 가리기 위해 참가자들이 받은 점수 중 가장 높은 점수를 구해보자.

첫 번째 줄에 참가자의 수 $N$이 주어진다. ($1 \le N \le 1\,000$)

다음 $N$개의 줄에 각 참가자의 점수 $a$, $d$, $g$가 공백으로 구분되어 주어진다.

• $a$는 애드혹 문제를 해결해 얻은 점수이다. ($0 \le a \le 10\,000$)
• $d$는 다이나믹 프로그래밍 문제를 해결해 얻은 점수이다. ($0 \le d \le 10\,000$)
• $g$는 그리디 알고리즘 문제를 해결해 얻은 점수이다. ($0 \le g \le 10\,000$)
• $a$, $d$, $g$는 모두 정수이다.

첫 번째 줄에 참가자들이 받은 점수 중 가장 높은 점수를 출력한다.