Thang máy vũ trụ ( ELEVATOR )

Giới hạn
  • Thời gian: 1.013s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

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
  • Điểm: 0.13
  • Ngôn ngữ cho phép:
  • Nguồn bài: USACO 3/2005