说明

众所周知，自古对波左边必输，为了打破这种定律，只要让所有放波的人都站在左边就好了。

现在有N个奥特曼需要站成一排，每个奥特曼都有自己的三维属性，分别是力量Xi，敏捷Yi，智力Zi。每个奥特曼会对右边的所有人造成（敏捷+智力）的伤害；而自身的力量值会抵消等额的来自左边奥特曼的伤害。但奥特曼们是好兄弟，不想让某一个奥特曼受到的伤害过大。因此他们需要重新排队，保证受到伤害最大的那个奥特曼所受到的伤害尽可能小。

输入格式

第一行输入一个整数N，表示奥特曼的个数。（1 <= N <= 50000）

之后N行，每行三个正整数数Xi，Yi，Zi，表示第i个奥特曼的力量、敏捷、智力值。(0 <= Xi，Yi，Zi <= 10000)

输出格式

输出一个整数，表示受到伤害最大的那个奥特曼所受到的尽可能小的伤害值。

样例

3
3 3 7
5 1 1
3 1 2

2

提示

可以得到，样例中最优排序是[3, 2, 1]，即三维属性（3,1,2）的排在第一位，（5,1,1）的排在第二位，（3,3,7）的排在第三位。这样他们受到的伤害分别为[0, 0, 2]，受到的最大伤害为2，在所有排序方案中该伤害最低。