1920: 地铁建设
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：52
解决：45
题目描述
某地铁沿线共设N 站，可分为U（地面式）、D（地下式）和C（复合式）三种类型。为避免单调，相邻地铁站的类型不能重复。同时，由于地铁站所处环境和地质条件有所差异，每个站点按不同类型的建设成本也不尽相同。现给定各站点的三种建设成本，请计算出该地铁线的最低总造价。
输入
包含N+1 行：
第1 行为一个正整数，表示地铁站的总数N。
第2 行到第N+1 行分别包含用空格分隔的三个正整数U，D 和C。其中第i+1 行表示第i 个地铁站按U、D 或C 类型的建设成本，1 ≤ i ≤ N。
输出
只包含一个正整数，表示建成这N 个地铁站所需要的最低成本。
样例输入 复制
3
1 99 99
99 1 99
99 99 1
样例输出 复制
3提示
【数据规模与约定】
对于20%的数据，N ≤ 10；
对于40%的数据，N ≤ 1000；
对于100%的数据，N ≤ 200000，1 ≤ U, D, C ≤ 10000。