bzoj#P1739. [Usaco2005 mar]Space Elevator 太空电梯

[Usaco2005 mar]Space Elevator 太空电梯

题目描述

The cows are going to space! They plan to achieve orbit by building a sort of space elevator:
a giant tower of blocks. They have k (1k400)k \ (1 \le k \le 400) different types of blocks with which to build the tower. Each block of type ii has height hi (1hi100)h_i \ (1 \le h_i \le 100) and is available in quantity ci (1ci10)c_i \ (1 \le c_i \le 10). Due to possible damage caused by cosmic rays, no part of a block of type ii can exceed a maximum altitude ai (1ai4×104)a_i \ (1 \le a_i \le 4\times 10^4). Help the cows build the tallest space elevator possible by stacking blocks on top of each other according to the rules.

牛们要到太空去了!他们打算建造一座太空电梯来送他们进入轨道。
kk 种方块,第 ii 种有一个特定的高度 hih_i,一定的存量 cic_i. 为防宇宙射线的破坏,第 ii 种方块的任何部分不能超过高度 aia_i。请用这些方块堆出最高的太空电梯。

输入格式

  • Line 11: A single integer, kk.
  • Lines 2k+12 \ldots k+1: Each line contains three space-separated integers: hi,aih_i,a_i, and cic_i. Line i+1i+1 describes block type ii.
  • 第一行输入一个整数 kk
  • 接下来 kk 行,每行输入三个整数 hi,ai,cih_i,a_i,c_i

输出格式

  • Line 11: A single integer hh, the maximum height of a tower that can be built.
  • 一个整数,表示最大高度。
3
7 40 3
5 23 8
2 52 6
48

样例说明

从底部开始,先放 33 个方块 22,之后 33 个方块 11,接下来 66 个方块 33。不能把 33 个方块 11 堆到 44 个方块 22 上,因为这样最高的方块 11 的顶部高度超过了 4040

数据规模与约定

对于 100%100\% 的数据,1k4001 \leq k \leq 4001hi1001 \leq h_i \leq 1001ci101 \leq c_i \leq 101ai4×1041 \leq a_i \leq 4\times 10^4

题目来源

Gold