一家杂货店有 种不同的商品，将它们从上到下堆成一条竖直货堆。每种商品都有三种参数： 重量 ； 初始体积 ； 压缩系数 。 当商品被压在其他货物之下时会发生压缩：设商品 上方（不含自身）的总重量为 ，则该商品的实际体积变为 。 店铺空间有限，店主想合理安排堆放顺序，使所有商品实际体积之和 尽可能小。

输入描述:

第一行输入整数 ——商品数量。接下来 行，第 行输入三个整数 ，满足 ； ； 。保证任何合法堆叠下均有 。

输出描述:

输出一个整数，表示最小可能的实际体积总和。