주식 투자

환규는 오늘부터 주식 투자를 시작한다. 정보를 모아 본 결과 A사, B사, C사에 투자하기로 했다. 오늘 산 주식이 내일 오를지 떨어질지 예측하기는 아직 어려워서, 다음 규칙대로 투자한다.

• 하루에는 최대 한 회사의 주식만 산다. 날마다 다른 회사를 골라도 된다.
• 매일 장이 열리기 전에 A사, B사, C사 중 그날 주식을 살 회사를 하나 정하고, 장이 열릴 때 그 회사의 주식을 산다.
• 장이 닫힐 때 그날 산 주식을 모두 판다.
• 세 회사 중 어느 곳도 수익이 날 것 같지 않으면 그날은 주식을 사지 않아도 된다.

환규는 투자하려는 회사의 지난 $N$일 주가 데이터를 모아, 회사별로 장이 열릴 때 사서 장이 닫힐 때 모두 팔았다면 그날 얼마를 벌었을지 정리했다. $N = 4$일 때 정리한 표는 다음과 같다.

표의 양수는 이익, 음수는 손해를 나타내고, 0은 이익도 손해도 없음을 뜻한다. 1일째에 A사 주식을 장이 열릴 때 사서 장이 닫힐 때 팔면 500의 이익이 남고, 3일째에 C사 주식을 같은 방식으로 사고팔면 400의 손해가 난다.

이 표에서 최적으로 투자하면 1일째에는 B사를 사고, 2일째에는 A사나 C사를 사고, 3일째에는 어떤 주식을 사도 손해이므로 사지 않고, 4일째에는 A사를 산다. 이렇게 하면 800 + 300 + 0 + 600 = 1700으로 이익이 가장 크다.

$N$일 동안 A사, B사, C사의 주식을 장이 열릴 때 사서 장이 닫힐 때 모두 팔았을 경우의 손익 데이터가 주어진다. 환규가 규칙을 지키며 최적으로 투자했을 때 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.

입력은 표준 입력을 사용한다. 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 주식 데이터의 일수를 나타내는 자연수 $N$ ($1 \le N \le 1000$)이 주어진다. 이어지는 $N$개의 줄에는 그날 각 회사의 주식을 사고팔았을 때의 손익을 나타내는 세 정수 $A$, $B$, $C$ ($-1000000 \le A, B, C \le 1000000$)가 주어진다. $A$는 A사, $B$는 B사, $C$는 C사의 손익이다.

출력은 표준 출력을 사용한다. 각 테스트 케이스마다 환규가 $N$일 동안 규칙을 지키며 최적으로 투자했을 때 얻을 수 있는 최대 이익을 한 줄에 하나씩 출력한다.