Có \(N\) viên gạch được đánh số \(1,2,3,...,N\). Với mỗi \(i\) \((1\le i\le N)\), viên gạch thứ \(i\) có khối lượng là \(w_i\), độ cứng \(s_i\) và giá trị là \(v_i\).

Kaninho quyết định xây một tòa tháp bằng một số viên gạch được chọn từ \(N\) viên gạch trên và xếp chúng theo chiều thẳng đứng. Biết rằng tòa tháp này phải thỏa mãn điều kiện sau:

• Với mỗi viên gạch \(j\) được chọn, thì tổng khối lượng của tất cả những viên gạch được xếp trên nó phải không được lớn hơn \(s_j\).

Tìm tổng giá trị lớn nhất của các viên gạch được chọn để xây tòa tháp.

Input

• Dòng thứ nhất chứa số nguyên \(N\) \((1\le N\le 10^3)\).
• \(N\) dòng tiếp theo chứa ba số nguyên \(w_i, s_i, v_i\) \((1\le w_i, s_i\le 10^4, 1\le v_i\le 10^9)\).

Output

• In ra giá trị cần tìm.

Example

3
2 2 20
2 1 30
3 1 40

50

Nguồn: Tham khảo từ Atcoder