Hôm nay Roronoa Zoro, thợ săn quỷ mạnh nhất đang đến tiki shop để mua nhận luân kiếm cho trận chiến sống còn với chúa quỷ Muzan sắp tới. Khi Zoro tới thì chủ tiệm là algorit đang loay hoay xếp kiếm, algorit mãi chưa xếp xong kiếm nên đành nhờ Zoro giúp xếp hộ kiếm.

Trong tiệm \(N\) thanh kiếm có trọng lượng , độ dài , độ cao lần lượt là \(C_i , W_i , H_i\) , chiều rộng của mỗi thanh kiếm bằng với chiều rộng của tủ kiếm. Trọng lượng và độ dài của mỗi ngăn mà tủ kiếm có thể chứa là \(P\) và \(Q\) .

Bây giờ algorit muốn nhờ Zoro chia \(N\) hộp thành các đoạn liên tiếp để xếp vào ngăn. Biết độ cao của mỗi ngăn là độ cao của thanh kiếm cao nhất trong các hộp đã được xếp vào ngăn. Nếu Zoro giúp được thì algorit sẽ tặng cho anh \(1\) thanh kiếm Trung Quốc hàng xịn, hãy giúp anh ấy nhé !

• Yêu cầu : Hãy tính chiều cao tối thiểu của tủ khi xếp các kiếm vào tủ 1 cách tối ưu .

Input

• Dòng đầu tiên gồm 3 số nguyên dương \(N , P , Q\) . \((N \le 9999, (P,Q) \le 10^{12})\)
• N dòng tiếp theo gồm 3 số nguyên dương \(C_i , W_i , H_i\) . \((C_i \le P,W_i \le Q,H_i \le 10^9)\)

Output

• Gồm 1 số nguyên dương duy nhất là kết quả của bài toán .

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \le 400 , P \le 10^3 , Q \le 10^3 , H_i \le 10^3 .\)
• Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm .*

Example

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

12