Background

Special for beginners, ^_^

Description

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

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

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

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

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

Format

Input

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

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

Output

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

Limits

10≤n≤50 n≤N≤100

Samples

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

Limitation

1s, 1024KiB for each test case.