Mall

时间限制:20s      空间限制:256MB

题目描述

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

提示

没有写明提示


题目来源

没有写明来源