Farmer John và đàn bò đang chơi ném đĩa. Bessie ném chiếc đĩa xuống cánh đồng, nhưng nó đang bay thẳng về phía Mark, người làm công thuộc đội đối thủ! Mark cao \(H\) (\(1 \le H \le 1\,000\,000\,000\)), nhưng có \(N\) cô bò thuộc đội Bessie đang tụ tập quanh Mark (\(2 \le N \le 20\)). Họ chỉ có thể bắt được chiếc đĩa nếu chồng lên nhau để đạt độ cao ít nhất bằng Mark. Mỗi cô bò trong số \(N\) cô bò có một chiều cao, khối lượng và sức chịu đựng. Sức chịu đựng của một cô bò cho biết tổng khối lượng tối đa của những cô bò có thể được xếp phía trên cô ấy.

Với các điều kiện này, Bessie muốn biết đội của mình có thể dựng một chồng bò đủ cao để bắt chiếc đĩa hay không; nếu có, hệ số an toàn lớn nhất của một chồng như vậy là bao nhiêu. Hệ số an toàn của một chồng bò là khối lượng có thể đặt thêm lên đỉnh chồng mà không vượt quá sức chịu đựng của bất kỳ cô bò nào.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(H\).

\(N\) dòng tiếp theo, mỗi dòng mô tả một cô bò bằng chiều cao, khối lượng và sức chịu đựng của cô ấy. Tất cả đều là các số nguyên dương không vượt quá 1 tỷ.

Dữ liệu ra

Nếu đội của Bessie có thể dựng một chồng bò đủ cao để bắt chiếc đĩa, hãy in ra hệ số an toàn lớn nhất có thể đạt được của một chồng như vậy. Nếu không, in ra Mark is too tall (không gồm dấu ngoặc kép).

Ví dụ

4 10
9 4 1
3 3 5
5 5 10
4 4 5

2

Nguồn

USACO 2014 December Contest, Gold — Guard Mark. Tác giả đề: Bill Cooperman, 2014.

https://usaco.org/index.php?page=viewproblem2&cpid=494