133. Day 2 PC. 什麼之塔

什麼之塔

題目敘述

什麼之塔是一個古老且充滿挑戰關卡的高塔，吸引了許多勇猛的冒險者前來挑戰，不過能成為勇猛的冒險者的人少之又少，因此一群實力比較沒有那麼堅強的村民想要直接挑戰什麼之塔是不可能的事，因此他們想到了一個繞過塔內關卡的方法，他們要在塔外的牆上建造一個垂直的梯子當作捷徑，就能避免塔內的關卡試煉了！

已知他們有$K$種不同的梯子，第$i$種的梯子有$a_i$個，高度為$h_i$。把兩個梯子接在一起時，新梯子的高度就是原本兩梯子的高度和，十分簡單，只要能把所有梯子串在一起，就能建造直達終點的捷徑！

不過這個願望被新的發現而瓦解了，因為什麼之塔塔外偶爾會突然出現神秘的力場，粉碎無法承受該立場的所有物質，比如說：用來搭捷徑的梯子，根據測試的結果，第$i$個梯子只能安全的放置在小於等於高度$t_i$的位置，如果有任何一個部分超出該高度，該段梯子的結構就會瓦解，讓辛苦搭建捷徑就會垮下來，十分危險。因此身為監督的你，被賦予任務計算使用這些提供的材料時，最高可以建立多高的梯子，為了大家的意志，這份重責大任就交給你了。

輸入說明

輸入的第一行有一個正整數$K$，代表有幾種種類的梯子。接下來有$K$行，每行有3個整數$h_i~t_i~a_i$，第i行表示第i個梯子的資料。

• $1\leq K \leq 400$
• $1\leq h_i \leq 100$。
• $0\leq t_i \leq 40000$。
• $0\leq a_i \leq 10$。

輸出說明

請輸出最高可以建立的捷徑梯子高度為何。

範例輸入

3
7 40 3
5 23 8
2 52 6

範例輸出

48

提示

Tip:DP。

Judge Setting

run-time limit: 50 ms
memory limit: 65536 byte
測資數量: 0