Xếp tháp
An đang chơi xếp tháp. An có tất cả $N$ khối gỗ. Khối gỗ thứ $i$ có trọng lượng $w_i$, khả năng chịu đựng $s_i$ và chiều cao $h_i$.
Một khối gỗ đặt được trên một chồng gỗ nếu mỗi khối gỗ trong chồng có khả năng chịu đựng lớn hơn hoặc bằng tổng trọng lượng của các khối gỗ nằm trên nó và khối gỗ sắp đặt lên.
An muốn xếp được một tháp gỗ có chiều cao ít nhất là $H$. Hãy cho cậu biết, tháp gỗ thỏa mãn điều kiện có thể chịu đựng thêm trọng lượng tối đa bao nhiêu?
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N, H \ (0<N\le 20; 0<H\le10^9) $;
- $N$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $h_i, w_i, s_i \ (0 < h_i,w_i,s_i \le 10^9)$.
.
Kết quả
- Kết quả bài toán.
Ví dụ
Ví dụ 1
input
4 10
3 3 5
9 4 2
5 5 10
4 4 5
output
2
Comments