题目描述

Bessie 喝完 $n$ 瓶饮料把透明的瓶子排成一排，想把这些饮料瓶子都涂上颜色。她觉得如果所有相邻的两个瓶子颜色都不一样的话会比较有趣。她现在只有红色 $(Red)$、绿色 $(Green)$ 和蓝色 $(Blue)$ 这三种颜料。由于瓶子的大小和表面材质不同，在不同的瓶子上涂不同的颜色需要的花费都不一样。Bessie 统计了一下， 把第 $i$ 个瓶子染成红色需要 $R_i$ 元钱，染成绿色需要 $G_i$ 元钱，染成蓝色需要 $B_i$ 元钱。现在请你帮她计算出要使相邻两个瓶子的颜色都不一样，至少需要多少花费。

格式

输入格式

第一行为正整数 $t(≤5)$，表示数据组数；每组数据中，第一行为正整数 $n$， 接下来 $3$ 行，每行 $n$ 个正整数 $r_i（g_i,b_i）$，分别表示把第 $i$ 个瓶子染成红色（绿色，蓝色）的花费，$n≤10^5，r_i,g_i,b_i≤100$。

输出格式

对于每组数据，输出最少花费。

样例1

输入样例1

2
5
1 3 1 2 2
1 2 3 4 3
4 2 1 5 3
10
10 5 10 9 7 9 4 6 7 9
4 8 9 2 5 10 4 7 1 9
8 8 7 9 5 5 9 3 1 8

输出样例1

9
46

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛$T4$

文件IO

freopen("paint.in","r",stdin);
freopen("paint.out","w",stdout);