在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了N堆。果园是一个二维平面，第i堆果子的位置为(Xi,Yi)，重量为Wi。 多多决定把所有的果子合成一堆。每一次合并，多多可以消耗Wi (Xi - Xj +Yi - Yj )的体力把第i堆果子合并到第j堆。可以看出，所有的果子经过N-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 请你求出将所有果子合并成一堆消耗的总体力最少是多少。

输入描述:

第一行一个正整数N，接下来N行每行三个正整数 Xi Yi Wi

输出描述:

一个数，最少消耗的总体力