题目描述

XP的百货商场很快就要开张啦，他希望能够确保百货商场的安全。 商场包括 $n$ 层，从 $1$ 到 $n$ 标号，每层楼都有一些小商店供顾客选购商品。百货商场的电梯连接着相邻的两层楼的商店（我们不妨假设 $1$ 楼到 $n$ 楼也是相邻的），对于每一层楼，一共有 $K_{i}$ 个小商店，从 $1$ 到 $K_{i}$ 标号。而百货商场总共有 $N$ 个小商店。XP希望安置一些警卫在商店里看守，但是他有两个要求：

• 一个商店最多由一个警卫看守
• 电梯的两端不能同时放置警卫进行看守 在满足条件的情况下，XP想知道最多能安置多少个警卫。

输入格式

输入第一行一个整数 $n$，表示百货商场有 $n$ 层。 接下来若干行，每行若干个数，每 $3$ 个数代表一个电梯。其中 $A,B,C$ 表示由一个电梯从第 $C$ 层的 $A$ 号房连向第 $C+1$ 层的 $B$ 号房（第 $n$ 层连向第 $1$ 层）。

输出格式

输出一个整数，表示最多能安置的警卫个数。

数据范围

$10\le n \le 50,n \le N \le 100$

10
1  1  1  1  1  2  1  1  3  1  1  4  1  1  5  1  1  6  1  1  7  1  1  8  1  1  9  1  1  10

5

提示

没有写明提示

题目来源

没有写明来源