Atcoder Educational DP Contest X - Tower

View as PDF

Submit solution


Points: 1.25 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.