문제 설명
세종이네 고등학교에서는 매년 배드민턴 대회를 주최한다. 대회는 개인과 복식 총 \(2\)개의 부문이 있으며, 모든 학생들은 하나의 부문에 참가해야 한다. 개인전은 혼자 출전하는 종목이며, 팀전은 2명의 학생이 한 팀이 되어 출전하는 종목이다. 팀을 구성할 때에는 조건이 있는데 2명의 학생 모두 같은 반이어야 하며, 2명의 출석번호가 연속된 번호여야 한다. 예를 들어 1번 학생과 2번 학생은 한 팀이 될 수 있지만 1번 학생과 3번 학생은 한 팀이 될 수 없다.
세종이네 반 학생들은 혼자서 출전할 때와 팀으로 출전할 때의 기대치가 다르며, 어떤 학생과 한 팀이 되느냐에 따라 기대치가 달라진다. 세종이네 반 학생 수와 각각의 학생이 가진 기대치가 주어질 때, 세종이네 학급이 가질 수 있는 총 기대치의 최댓값을 구하는 프로그램을 작성하시오.
세종이네 반 학생들은 혼자서 출전할 때와 팀으로 출전할 때의 기대치가 다르며, 어떤 학생과 한 팀이 되느냐에 따라 기대치가 달라진다. 세종이네 반 학생 수와 각각의 학생이 가진 기대치가 주어질 때, 세종이네 학급이 가질 수 있는 총 기대치의 최댓값을 구하는 프로그램을 작성하시오.
입력 설명
첫째 줄에는 학생 수 \(N\)이 주어진다.
둘째 줄부터 \(N+1\)째 줄까지 \(N\)명의 학생들의 기대치\((T)\)가 번호 순서대로 주어진다.
기대치는 총 3개의 정수이며, 각각 앞번호 학생과 팀전에 출전할 때의 기대치, 뒷번호 학생과 팀전에 출전할 때의 기대치, 개인전에 출전할 때의 기대치를 의미한다. 팀을 구성한 사람의 조합이 같다면 기대치는 항상 동일하다. 만약 앞번호 학생/뒷번호 학생이 없는 경우에는 기대치가 0이 입력된다.
\(1 \le N \le 20, 0 \le T \le 1,000)\)
둘째 줄부터 \(N+1\)째 줄까지 \(N\)명의 학생들의 기대치\((T)\)가 번호 순서대로 주어진다.
기대치는 총 3개의 정수이며, 각각 앞번호 학생과 팀전에 출전할 때의 기대치, 뒷번호 학생과 팀전에 출전할 때의 기대치, 개인전에 출전할 때의 기대치를 의미한다. 팀을 구성한 사람의 조합이 같다면 기대치는 항상 동일하다. 만약 앞번호 학생/뒷번호 학생이 없는 경우에는 기대치가 0이 입력된다.
\(1 \le N \le 20, 0 \le T \le 1,000)\)
출력 설명
세종이네 반이 가질 수 있는 기대치의 최댓값을 출력한다.
입력 예시 Copy
5
0 14 10
14 25 5
25 34 30
34 5 2
5 0 7
출력 예시 Copy
56