#14. 梅开三度

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: syzoj

题目描述

出题人: HANSAMA

理工大学的生物是非常好的专业,优秀学子小吴在一次实验时,发现了一种神奇的长得像梅花的奇怪物质,叫他梅纹花。经过一段时间的研究,他发现这个物质有三种属性,分别是毁灭,美丽和快乐,这三种属性分别以一个正整数表示,当小吴尝试将两个梅纹花融合成一个时,他发现融合后数值上的变化不是线性的。这难倒了小吴,于是他找到了好盆友,来自计算机系的小派,经过小派严谨的推理和分析,他发现了如下变化规律:

毁灭的融合是 “异或运算”,因为否极泰来负负得正;

美丽的融合是 “与运算”,因为大家总是看到你最丑的那个部分;

快乐的融合是“或运算”,因为快乐是会传递的。

在试验的过程中,小派还发现,当美丽和快乐数值相同的时候,梅纹花会变得油润起来,又名油纹花。而且这个时候可以用美丽与毁灭的差的绝对值的十进制数值表示中o的数量来描述油纹花的不稳定性(数值越大越不稳定)。现在小吴有k个梅纹花依次排列,他每次可以将相邻的梅纹花进行融合,融合之后原来的两个梅纹花将由融合之后的一个梅纹花取代,三项属性也根据上述运算规则合并。请问小吴最理想的状态下,用当前的梅纹花可以合成出的最稳定的油纹花的稳定性是多少,如果不能合成出油纹花,返回 -1

输入格式

输入总共 k 行。

第一行输入 k ,代表 k 个梅纹花。

接下来k行每行输入三个数 H_i, M_i, K_i ,分别代表这个梅纹花的毁灭值,美丽值和快乐值。

输出格式

输出能合成出的所有的油纹花的稳定性中的最小值,

如果不能合成,输出 -1

样例

Sample Input 1

6
31 1 31
27 16 27
1 17 17
17 17 17
16 27 16
1 31 1

Sample Output 1

0

Sample Input 2

2
31 1 31
27 16 27

Sample Output 2

-1

数据范围与提示

数据范围:

1 \le k \le 10^5

0 \le H_i, M_i, K_i \lt 10^6