Description

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

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

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

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

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

Input

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

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

Output

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

Limits

10≤n≤50        n≤N≤100

Sample Input

Sample Output

Hint

Source