Description

朱迪警官需要驾驶巡逻车依次通过 n 个动物城交通枢纽关卡，每个枢纽仅允许特定类型的巡逻车通行（共 3 种适配车型：兔型轻便车、狐型敏捷车、牛型载重车）。 初始阶段，朱迪需要花费 1 单位的警局调度经费申请一种初始巡逻车类型（仅能选择某一种）。在通过每个枢纽前，朱迪可以花费 1 单位经费更换为另一种巡逻车类型（仅能更换为当前枢纽允许通行的车型），也可以不花费经费保持当前车型。 请计算朱迪驾驶巡逻车顺利通过所有 n 个交通枢纽的最小总调度经费（初始申请经费 + 更换车型经费之和）。

Format

Input

第一行输入一个整数 $n（1 ≤ n ≤ 10^5）$，表示交通枢纽的数量； 接下来 $n$ 行，每行输入 $3$ 个整数（0 或 1），依次表示对应枢纽是否允许兔型轻便车、狐型敏捷车、牛型载重车通行（$1$ 表示允许，$0$ 表示禁止）。保证每行的 $3$ 个数不全为 $0$（即每个枢纽至少允许一种车型通行）。

Output

输出一个整数，表示通过所有枢纽的最小总调度经费。

Samples

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

3

Limitation

1s, 1024KiB for each test case.