logo AlgoBeat OnlineJudge
登录 注册

#214426. [LNCPC 2025] 点击平衡球

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

Z 形管道猫推荐您来玩平衡球(Ballance)。在游戏中,玩家要操纵一个可以改变自身材质(即物理性质)的球在由路面和机关构成的庞大而复杂的迷宫建筑中穿梭,避开陷阱、运用机关并破解一个个谜题,最终到达终点。


平衡球有 种材质(纸球、木球、石球)。在游戏中,平衡球需要通过 个机关,每个机关各自只允许特定一些材质的平衡球通过。初始,您需要花费 单位的代价将平衡球选定为一种材质。在通过每个机关前,您可以花费 单位的代价将平衡球切换为另一种材质,也可以不花费代价保持当前材质。

现在您可以任意安排机关的通过顺序,请您求出平衡球通过这 个机关所需的最小代价。

输入格式

第一行给定一个整数 ,表示机关总数。

接下来 行,每行给定三个整数 ,其中第 行的第 个整数 分别表示给定的第 个机关不允许、允许第 种材质的平衡球通过。保证 不全为

输出格式

一个整数,表示经由合理安排机关的通过顺序和材质的代价花费,平衡球通过这 个机关所需的最小代价。

样例

样例输入 1

5
1 0 0
1 0 1
0 1 0
1 0 1
0 0 1

样例输出 1

3

数据范围与提示

一种机关的通过顺序和材质的代价花费的合理安排如下:
机关的通过顺序依次为给定的第 个机关。
初始,花费 单位的代价将平衡球选定为第 种材质。
在通过给定的第 个机关前,不花费代价保持当前材质。
在通过给定的第 个机关前,花费 单位的代价将平衡球切换为第 种材质。
在通过给定的第 个机关前,花费 单位的代价将平衡球切换为第 种材质。
在通过给定的第 个机关前,不花费代价保持当前材质。
在通过给定的第 个机关前,不花费代价保持当前材质。

可以证明,经由合理安排机关的通过顺序和材质的代价花费,平衡球通过这 个机关所需的最小代价是