题目描述

Poj 2392

很久以前,魔法世界的人们注重于眼前的享乐,失去了探索宇宙,探索未知世界的兴趣， 他们经常以急功近利的心态评价一件事:"这对我有什么用呢?"幸好当时的领导人远见卓 识，他说:"我们历史上曾经因错失大航海时代,而导致了长达数百年的衰落。今天,我们不 能再错失太空时代,我们的征途将是星辰大海!"所以现在魔法学院才能够有足够的技术实 力建造太空梯(用魔法石垒)进入太空以应对天顶星人的威胁。他们有$\red{k (1≤k≤400)}$种不 同类型的魔法石,每一种魔法石的高度为$\red{h(1≤}$$\red{h≤}$$\red{100),}$数量为$\red{c (1≤}$$\red{c≤}$$\red{10),}$由于会受到 太空辐射而失去魔力,每一种魔法石不能超过这种魔法石的最大建造高度$\red{a (1≤}$$\red{a_i≤}$ $\red{40000),}$求解利用这些魔法石所能修建的太空梯的最高高度。.

输入格式

第一行为一个整数即$\red{k}$。

第$\red{2}$行到第$\red{k+1}$行每一行有三个数,代表每种类型魔法石的 特征,即高度$\red{h,}$限制高度$\red{a}$和数量$\red{c}$。

输出格式

一个整数,即修建太空梯的最大高度。

样例

输入样例

3
7 40 3
5 23 8
2 52 6

输出样例

48

提示

$\red{15+21+12}$

最底下为$\red{3}$块石头$\red{2}$型,中间为$\red{3}$块石头$\red{1}$型,上面为$\red{6}$块石头$\red{3}$型。放置$\red{4}$块石头$\red{2}$ 型和$\red{3}$块石头$\red{1}$型是不可以的,因为顶端的石头$\red{1}$型的高度超过了$\red{40}$的限制。