3216 - 房子涂色

一排房子需要涂色,颜色可以选红、绿、蓝,每栋房子涂不同的颜色的费用不同。相邻房子不允许涂相同的颜色。求如何涂色使得涂色总费用最小。

输入

第一行为整数n,表示n栋房子。 第二行至第四行分别为为n栋房子涂红色、绿色、蓝色所需要的费用。

输出

一个整数,表示最小总费用。

样例

输入

3
14 2 11
11 14 5
14 3 10

输出

18

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题