问题 3156 --太空梯

3156: 太空梯

题目描述

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

输入

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

输出

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

样例输入输出

输入#1 复制
3
7 40 3
5 23 8
2 52 6
输出#1 复制
48

提示

【样例说明】
15+21+12
最底下为3块石头2型,中间为3块石头1型,上面为6块石头3型。放置4块石头2型和3块石头1型是不可以的,因为顶端的石头1型的高度超过了40的限制。

序号 标题 作者 发表时间 费用 订购数 操作