该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

地铁(subway)

题目描述

某地铁沿线共设 N 站，可分为 U（地面式）、D（地下式）和 C（复合式）三种类型。为避免单调，相邻地铁站的类型不能重复。同时，由于地铁站所处环境和地质条件有所差异，每个站点按不同类型的建设成本也不尽相同。现给定各站点的三种建设成本，请计算出该地铁线的最低总造价。

输入格式

包含 N+1 行：

第 1 行为一个正整数，表示地铁站的总数 N。

第 2 行到第 N+1 行分别包含用空格分隔的三个正整数 U，D 和 C。其中第 i+1

行表示第 i 个地铁站按 U、D 或 C 类型的建设成本，1 ≤ i ≤ N。

输出格式

只有一行：包含一个正整数，表示建成这 N 个地铁站所需要的最低成本。

样例 #1

样例输入 #1

3
1 99 99
99 1 99
99 99 1

样例输出 #1

3

提示

【限制】

1 ≤ N ≤ 1,000,000，1 ≤ U, D, C ≤ 1,000