题目描述

走出了迷宫后,阿什尼终于找到了美味的食材:史莱姆鱼.它们是漂浮在空中(没有重量)的一种鱼类.

阿什尼准备捕捉史莱姆鱼回饭店。现在，他在一群有史莱姆鱼的旁边。这里有$n$条史莱姆鱼，把第$i$条史莱姆鱼弄回饭店需要 $t_i*2$ 个单位的时间（毕竟需要往返）。

但是这些史莱姆鱼一量发现自己的同伴丢失了就会生气,吸入大量的空气,从而改变自己的重量！随着时间的推移,这些鱼会越来越重，第$i$鱼的脾气为$c_i$,在时刻$t$,第$i$条鱼的重量为$t * c_i$.

阿什尼把它们弄回来所消耗的体力与鱼的重量成正比，即在第 $t$ 个时刻开始运第 $i$ 条史莱姆鱼所消耗的体力为 $t*c_i$ 。一开始所有的史莱姆鱼都没有重量.也就是说运送第一条史莱姆鱼所消耗的体力为 $0$ 。

阿什尼想知道把所有史莱姆鱼运回饭店所消耗的体力最少是多少

输入格式

第一行输入一个整数 $n$，表示史莱姆鱼的数量。

接下来$n$行，每行包含两个整数 $t_i,c_i,t_i$

输出格式

一个整数，表示最少消耗的体力。

输入样例

6
3 1
2 5
2 3
3 2
4 1
1 6

输出样例

86

数据范围与提示

对于 $10\%$ 的数据，$n \leq 10,t \leq 100,ci \leq 10$ ；

对于 $60\%$ 的数据，$n \leq 1000,t \leq 20000,ci \leq 100$ ；

对于 $100\%$ 的数据，$n \leq 100000,t \leq 2000000,ci \leq 100$