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 \leq K \leq 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 \leq h_i \leq 100)~ và có số lượng ~c_i~ ~(1 \leq c_i \leq 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 \leq a_i \leq 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

Một dòng dòng duy nhất là độ cao lớn nhất của tháp có thể xây được

Sample Input

3
7 40 3
5 23 8
2 52 6

Sample Output

48

Note

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~ và ~3~ khối loại ~1~ không hợp lệ vì đỉnh của khối loại ~1~ vượt quá độ cao 40.