Cho ~N~ khối khác nhau được đánh số từ ~1~ tới ~N~. Khối thứ ~i~ (~1 \le i \le N~) có cân nặng ~w_i~, có sức chịu nặng ~s_i~, và có giá trị ~v_i~.

Taro quyết định xây một toà tháp bằng một số khối lấy từ ~N~ khối đã cho và xếp chồng chúng lên nhau theo một thứ tự nhất định. Toà tháp phải thoả mãn điều kiện sau:

• Tổng khối lượng các khối được đặt trên khối thứ ~i~ không được phép lớn hơn ~s_i~.

Tìm tổng giá trị tối đa mà toà tháp có thể đạt được.

Input

• Dòng đầu tiên chứa số nguyên ~N~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa 3 số nguyên ~w_i, s_i, v_i~ lần lượt là cân nặng, sức chịu nặng và giá trị của khối thứ ~i~.

Output

Tổng giá trị tối đa mà toà tháp có thể đạt được.

Giới hạn:

• Mọi giá trị từ input đều là số nguyên.
• ~1 \le N \le 10^3~
• ~1 \le w_i, s_i \le 10^4~
• ~1 \le v_i \le 10^9~

Sample 1

Input

3
2 2 20
2 1 30
3 1 40

Output

50

Giải thích

Nếu như khối ~2~ xếp chồng lên khối ~1~, ta được tổng giá trị tối đa của toà tháp là ~30 + 20 = 50~.

Sample 2

Input

4
1 2 10
3 1 10
2 4 10
1 6 10

Output

40

Giải thích

Các khối ~1, 2, 3, 4~ được xếp theo thứ tự từ đỉnh tới đáy.

Sample 3

Input

5
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000

Output

5000000000

Kết quả có thể không phù hợp với số nguyên có định dạng 32-bit.

Sample 4

Input

8
9 5 7
6 2 7
5 7 3
7 8 8
1 9 6
3 3 3
4 1 7
4 5 5

Output

22

Giải thích

Chúng ta có thể xếp các khối ~5, 6, 8, 4~ theo thứ tự từ đỉnh tới đáy.