Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ELEVATOR - Thang máy vũ trụ

Những con bò muốn đi vào vũ trụ! Chúng muốn đến được quỹ đạo bằng cách xây một kiểu thang máy: một cái tháp khổng lồ làm bằng các khối chồng lên nhau. Chúng có K (1 ≤ K ≤ 400) loại khối có thể xây tháp. Mỗi khối loại i có chiều cao h_i (1 ≤ h_i ≤ 100) và có số lượng c_i (1 ≤ c_i ≤ 10). Do khả năng bị phá hủy bởi các tia vũ trụ, không có phần nào của khối loại i có thể vượt qua độ cao a_i (1 ≤ a_i ≤ 40000).

Giúp những con bò xây thang máy cao nhất có thể bằng cách chồng các khối lên nhau theo luật trên.

Input

* Dòng 1: Một số nguyên: K

* Dòng 2..K+1: Mỗi dòng chứa 3 số nguyên được phân cách bởi khoảng trắng: h_i, a_i, và c_i. Dòng i+1 miêu tả loaị khối i.

Output

* Dòng 1: Một số nguyên H, chỉ độ cao lớn nhất của tháp có thể xây được.

Example

Input:
3
7 40 3
5 23 8
2 52 6


Output:
48
GIẢI THÍCH:

Từ dưới lên: 3 khối loại 2, 3 khối loại 1, 6 khối loại 3. Chồng 4 khối loại 2 & 3 loại 1 không hợp lệ vì đỉnh của khối loại 1 vượt quá độ cao 40.


Được gửi lên bởi:Nguyen Dinh Tu
Ngày:2006-09-10
Thời gian chạy:1.013s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:USACO 3/2005

hide comments
2016-07-30 06:51:16 Sơn Tùng M-TP
So surprised!
2015-08-14 03:54:58
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/08/14/thang-may-vu-tru-elevator/

Last edit: 2015-09-13 07:51:47
2015-03-20 16:46:58 Prismatic
O(n*c[i]*a[i]) :3 cũng gọn :v
2015-01-28 02:14:35 lucky++
Bài hay, có bẫy, vừa giống cái túi lặp vật, vừa giống trạng thái.
2015-01-18 09:03:49 [deleted]
test rất rất yếu -_-
2014-11-16 15:56:40 livw
QHĐ chuẩn
2014-11-16 13:13:26 Change The World
QHD CHUẨN
2014-11-12 05:19:15 [CHV] Bác Thợ Sãn
t buồn lắm
2014-06-29 15:55:46 Nắng
AC sau gần 4 tháng mò mẫm :((
2014-03-07 05:56:37 Thanga2pbc
@

Last edit: 2014-03-07 05:56:59
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.