题目描述

有 $\red{2n }$个人玩拔河，拔河的绳子由左右两段组成，每段绳子上有 $\red{n }$个位置，第 $\red{i }$个人可以在左边绳子的 $\red{l_i }$位置处，也可以在右边绳子的 $\red{r_i }$位置处。

每个位置上有且仅有一个人。

每个人有一个实力值 $\red{s_i ，}$问对于每一种合法方案两边实力值和之差的绝对值最小是多少，如果无解输出 $\red{-1 }$。

输入格式

第$\red{1}$行一个整数 $\red{n}$。

第$\red{2...}$ $\red{2n+1}$行，每行三个整数$\red{l_i, r_i, s_i }$

输出格式

一个整数表示所求的答案

样例

输入样例

6

1 4 12

6 1 3

2 4 5

3 1 13

2 6 15

4 2 8

5 6 9

5 2 14

3 3 5

6 5 10

4 5 15

1 3 13

输出样例

6

提示

数据范围

$\red{30\%：}$$\red{1 <= n <= 10}$

$\red{70\%：}$$\red{1 <= n <= 10^3}$

$\red{100\%：}$$\red{1 <= n <= 3 \times 10^4, 1 <= s_i <= 15}$