cho.sh

Line of Bentham

줄에 선 사람 일부를 요원으로 바꿔, 각자가 앞의 세 명에게 느끼는 호감 합으로 정의된 총 행복을 최대로 만든다.

보통7동적 계획법그리디아직 제출이 없습니다시간 제한1초메모리 제한256 MB

문제

N명의 사람이 앞을 보고 일렬로 선다. 맨 앞이 1번이고 맨 뒤가 N번이다.

각 사람은 앞에 있는 최대 3명을 분간한다. ii번 사람이 jj번 사람을 좋아하는 정도를 정수 pi,jp_{i,j}로 재며 범위는 −10-10부터 1010까지이다. ii번 사람의 행복 지수는 qi=pi,i−3+pi,i−2+pi,i−1q_i = p_{i,i-3} + p_{i,i-2} + p_{i,i-1}이다. j≤0j \le 0인 경우 pi,j=0p_{i,j} = 0으로 둔다. 종합 행복 지수는 Q=∑i=1NqiQ = \sum_{i=1}^{N} q_i이다.

줄의 일부를 정부 파견 요원으로 바꿀 수 있다. 요원의 행복 지수는 00이고 요원은 뒤에 있는 사람의 행복 지수에 영향을 주지 않는다. 요원은 필요한 만큼 쓸 수 있다.

N명으로부터 얻을 수 있는 종합 행복 지수의 최댓값을 구한다.

입력

첫째 줄에 사람의 수 NN이 주어진다. 3≤N≤1,000,0003 \le N \le 1,000,000이다.

둘째 줄부터 NN개의 줄에 각 사람의 정보가 주어진다. ii번 사람에 대한 줄에는 정수 33개 pi,i−3p_{i,i-3}, pi,i−2p_{i,i-2}, pi,i−1p_{i,i-1}이 주어진다.

j≤0j \le 0인 pi,jp_{i,j}는 00으로 주어진다. 그 외의 pi,jp_{i,j}는 −10-10 이상 1010 이하의 정수로 주어진다.

출력

일부를 요원으로 바꾸어 얻을 수 있는 종합 행복 지수의 최댓값을 출력한다.

힌트

공개된 표본 입력에서 아무도 바꾸지 않으면 각 행복 지수는 00, 22, −3-3, 11이 되어 합이 00이다. 11번과 22번을 요원으로 바꾸면 합이 0+0+0+2=20 + 0 + 0 + 2 = 2가 되며 이보다 크게 만들 수는 없다.