题目描述

一切旅途总是那么美好，却也是那么短暂。

明明一家准备前往洛合总部进行一次奇妙的旅程，他们从一层走入总部，他们要到楼顶的观景台。

他们在每一层之间都有一个电梯，这个电梯可以帮助他们向上一层。当然，为了环保，他们也会走楼梯上一层楼。

在任意两层间，他们坐电梯会消耗 $x$ 点功德，走楼梯会消耗 $y$ 点功德。在他们到达楼顶时，请问如何使得功德剩余最大？

这太简单了，洛合早就算好了他们的路线，所以特地安排了直升电梯，并且拆除了原来的电梯。这些电梯途中不能停顿，所以自然无法上下电梯以减少功德。

功德消耗最少是多少？

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行 $3$ 个整数 $x$，$y$，$z$。

$x$ 和 $y$ 意义见题面，其中 $z$ 为该层所含有的可以乘坐或离开直升电梯个数。

输出格式

求出消耗功德最小值。

输入输出样例 #1

输入 #1

3
1 1 1
1 2 0
2 1 1

输出 #1

4

说明/提示

样例解释

只有一个电梯：$1$ -> $3$，所以走楼梯上到 $3$ 层和坐电梯功德损耗一样。

数据范围

对于 100% 的数据，$3 \le n \le 10^6$，$-10^6 \le x,y \le 10^6$，$0 \le z \le 10^6$。