题目描述

徐老师最近在玩一个游戏，在游戏中他拥有 $n$ 个随从 NPC

每个 $NPC$ 拥有三个属性：魅力，智力，武力

在这个游戏中，如果一个 $NPC$ 的三个属性分别大于等于另一个 $NPC$

那么我们说这个 $NPC$ 可以完美压制另一个 $NPC$

现在徐老师得到了一种特殊道具——强化药剂

这种药剂可以任选一个随从给他的任意一种属性强化，使得这项属性的数值 $+1$

徐老师每次可以进行两种操作：

1. 交换任意相邻的两名随从，使得他们的位置交换
2. 选择一名随从，给他使用一次强化药剂

而有强迫症的徐老师希望他最后的这 $n$ 个随从满足：对于相邻的两个随从来说，后一个随从可以完美压制前一个随从

即对于第 $i = 1 \sim n-1$ 个随从，满足第 $i + 1$ 个随从可以完美压制第 $i$ 个随从

现在徐老师想知道，最少需要花费几个强化药剂，可以满足他的要求？

输入格式

输入第一行包含一个整数 $n$ 表示随从人数

接下来 $n$ 行，每行包含三个整数 $a_i,b_i,c_i$ 分别表示第 $i$ 个随从的魅力值，智力值，武力值

输出格式

输出一个整数表示最少需要使用的强化药剂数量

数据范围

对于 $30\%$ 的数据保证：$1 \leq n \leq 5$。

对于另外 $20\%$ 的数据保证：所有随从的魅力相等，所有随从的智力相等

对于另外 $20\%$ 的数据保证：所有随从的魅力相等

对于 $100\%$ 的数据保证： $1\leq n \leq 250, 0 \leq a_i,b_i,c_i \leq 10^9$。

样例输入1

3
3 3 3
1 2 1
2 1 2

样例输出1

1

样例解释1

给 $3$ 号随从的智力强化 $1$ 次，他的属性变成 $2\ 2 \ 2$

最终排序为

1 2 1
2 2 2
3 3 3

样例输入2

5
1 2 3
2 3 1
1 3 3
4 5 6
5 5 5

样例输出2

3

样例解释2

最终排序为

1 2 3
1 3 3
2 3 3 (2次)
5 5 5
5 5 6 (1次)