Line of Bentham

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

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

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

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

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

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

$j \le 0$인 $p_{i,j}$는 $0$으로 주어진다. 그 외의 $p_{i,j}$는 $-10$ 이상 $10$ 이하의 정수로 주어진다.

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

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