Xếp Cột Bò

Có $N$ con bò đứng trên mặt đất. Bạn có thể chọn một tập con bất kỳ các con bò để xếp chồng lên nhau thành một cột. Mỗi con bò có chiều cao $h_i$, cân nặng $w_i$, và sức chịu đựng $s_i$ — là tổng cân nặng tối đa mà con bò đó có thể chịu đựng ở phía trên.

Cột hợp lệ khi mọi con bò trong cột đều chịu được tổng cân nặng của tất cả các con bò phía trên nó.

Hệ số an toàn của một cột là lượng cân nặng tối đa có thể thêm vào đỉnh cột mà không làm vượt quá sức chịu đựng của bất kỳ con bò nào.

Cho biết chiều cao mục tiêu $H$, hãy tìm hệ số an toàn lớn nhất có thể đạt được với một cột hợp lệ có tổng chiều cao $\ge H$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $H$.

• $N$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $h_i$, $w_i$, $s_i$ — chiều cao, cân nặng, và sức chịu đựng của con bò thứ $i$.

Dữ liệu ra

Một số nguyên — hệ số an toàn lớn nhất, hoặc Mark is too tall nếu không thể tạo cột hợp lệ có tổng chiều cao $\ge H$.

Ràng buộc

• $2\le N\le 20$
• $1\le H\le {10}^9$
• $1\le h_i,w_i,s_i\le {10}^9$

Ví dụ