ELEVATOR - Thang máy vũ trụ
Giới hạn- Thời gian: 1.013s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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.
- Người up: dtmp
- Nguồn bài: USACO 3/2005