题目描述

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

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

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

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

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

功德消耗最少是多少？

输入格式

第一行一个整数 $n$ 。

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

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

求出消耗功德最小值。

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

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