问题 1629. -- 瓶子涂色

1629: 瓶子涂色

时间限制: 1 Sec  内存限制: 128 MB
提交: 122  解决: 72
[提交][状态][讨论版]

题目描述

小猪上小学的时候,一度对颜色非常感兴趣,虽然他的美术非常糟糕。 
有一次他喝完n瓶饮料把透明的瓶子排成一排,想把这些饮料瓶子都涂上颜色。他觉得如果所有相邻的两个瓶子颜色都不一样的话会比较有趣。 
他现在只有红色(Red)、绿色(Green)和蓝色(Blue)这三种颜料。由于瓶子的大小和表面材质不同,在不同的瓶子上涂不同的颜色需要的花费都不一样。小猪统计了一下,把第i个瓶子染成红色需要Ri元钱,染成绿色需要Gi元钱,染成蓝色需要Bi元钱。 
现在请你帮他计算出要使相邻两个瓶子的颜色都不一样,他至少需要多少花费。

输入

第一行只有一个整数n,表示共有n只瓶子。 
第二行有n个正整数(以一个空格分隔),第i个数Ri表示把第i个瓶子染成红色需要Ri元钱。 
第三行有n个正整数(以一个空格分隔),第i个数Gi表示把第i个瓶子染成绿色需要Gi元钱。 
第四行有n个正整数(以一个空格分隔),第i个数Bi表示把第i个瓶子染成蓝色需要Bi元钱。 
( 1 ≤ n ≤ 100 000,1 ≤ Ri, Gi, Bi ≤ 100 )

输出

仅有一行,该行只有一个整数,表示最小花费。

样例输入

5 
1 3 1 2 2 
1 2 3 4 3 
4 2 1 5 3 

样例输出

9

提示

来源

[提交][状态]