1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using P=pair<int,int>;
int T,n;
int a[5];
int dp[100009][3][2];
void up(int &a,int b){
    if(a>b)a=b;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<=n;++i){
            for(int j=0;j<3;++j){
                for(int l=0;l<2;++l)
                    dp[i][j][l]=1000000000;
            }
        }
        dp[0][0][0]=0;
        for(int i=0;i<n;++i){
            scanf("%d%d%d%d%d",&a[0],&a[1],&a[2],&a[3],&a[4]);
            for(int j=0;j<3;++j){
                for(int l=0;l<2;++l){
                    up(dp[i+1][l][0],a[j+2]+dp[i][j][l]);
                    up(dp[i+1][l+1][0],a[j+1]+dp[i][j][l]);
                    up(dp[i+1][l][1],a[j+1]+dp[i][j][l]);
                    up(dp[i+1][l+1][1],a[j]+dp[i][j][l]);
                }
            }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX