#2236. Mall

内存限制:256 MiB 时间限制:20 Sec

题目描述

XP的百货商场很快就要开张啦,他希望能够确保百货商场的安全。

商场包括n层,从1n标号,每层楼都有一些小商店供顾客选购商品。百货商场的电梯连接着相邻的两层楼的商店(我们不妨假设1楼到n楼也是相邻的),对于每一层楼,一共有Ki个小商店,从1Ki标号。而百货商场总共有N个小商店。XP希望安置一些警卫在商店里看守,但是他有两个要求:

1.一个商店最多由一个警卫看守

2.电梯的两端不能同时放置警卫进行看守

在满足条件的情况下,XP想知道最多能安置多少个警卫。

输入格式

输入第一行一个整数n,表示百货商场有n层。

接下来若干行,每行若干个数,每3个数代表一个电梯。其中A,B,C表示由一个电梯从第C层的A号房连向第C+1层的B号房(第n层连向第1层)。

输出格式

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

Limits

10n50        nN100

样例

样例输入


			
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

数据范围与提示