Mall

XP 的百货商场即将开张，他希望确保商场的安全。

商场共有 $n$ 层，编号为 $1$ 到 $n$。每层都有一些商店供顾客选购商品。商场中的电梯连接相邻两层的商店，其中第 $1$ 层与第 $n$ 层也视为相邻。

第 $i$ 层共有 $K_i$ 个商店，编号为 $1$ 到 $K_i$。整个商场共有

$$N=\sum_{i=1}^{n}K_i$$

个商店。

XP 希望在一些商店中安排警卫，并须满足以下要求：

1. 每个商店最多安排一名警卫。
2. 同一部电梯连接的两个商店中，不能同时安排警卫。

请你求出满足上述条件时，最多可以安排多少名警卫。

输入格式

第一行输入一个整数 $n$，表示商场的楼层数。

此后直到文件结束，每三个整数 $A$、$B$、$C$ 描述一部电梯。该电梯连接第 $C$ 层的 $A$ 号商店与第 $C+1$ 层的 $B$ 号商店，其中第 $n+1$ 层视为第 $1$ 层。各三元组可以跨行排列。

对于每一层 $i$，保证至少有一个位于该层的商店编号在某部电梯的端点中出现。该层的商店数 $K_i$ 等于这些端点编号的最大值，因此该层商店的编号为 $1$ 到 $K_i$。

输出格式

输出一个整数，表示最多可以安排的警卫人数。

样例输入

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

数据范围

• $10\le n\le 50$；
• $n\le N\le 100$；
• 所有 $A$、$B$、$C$ 均符合题目所述的编号范围。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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