题目描述

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);