Máy bay tuần tiễu quân sự chiến lược trong một chuyến bay tuần tra đã gặp sự cố kỹ thuật. Tổ lái đã xử lý hết sức chuẩn mực, đưa được máy bay trở về căn cứ an toàn, nhưng một đầu đạn hạt nhân đã bị rơi xuống biển. Một lực lượng hùng hậu các tàu tìm kiếm được điều động tới khu vực dự kiến có đầu đạn thất lạc. Toàn bộ vùng biển được chia thành các băng, mỗi băng có độ rộng đơn vị. Để tránh các va chạm có thể xẩy ra giữa các tàu cũng như tránh nhiễu loạn tín hiệu dò tìm các tàu được chia thành ~n~ nhóm, nhóm thứ ~i~ có ~c_i ~ tàu ~(i = 1 \div n)~. Nhóm thứ ~i~ bắt đầu tìm kiếm ở băng ~a_i ~ và cứ sau một đơn vị thời gian tìm kiếm thì chuyển lên phía trước ~b_i ~ đơn vị độ dài, Như vậy nhóm thứ ~i~ thực hiện việc tìm kiếm ở các băng ~a_i, a_i + b_i, a_i+2b_i, a_i + 3b_i, . . .~
Có nhiều dấu hiệu cho thấy đầu đạn cần tìm có thể ở băng ~k~.
Yêu cầu:
Hãy xác định có bao nhiêu tàu đã thực hiện công việc tìm kiếm ở băng ~k~ và số tàu nhiều nhất tại một thời điểm cùng tìm kiếm ở băng ~k~.
Dữ liệu vào
- Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~k~ ~(1 \leq n \leq 10^5, 1 \leq k \leq 10^9)~,
- Dòng thứ ~i~ trong ~n~ dòng sau chứa ~3~ số nguyên ~a_i, b_i ~và ~c_i ~ ~(1 \leq a_i, b_i, c_i \leq 10^9)~.
Kết quả ra
Số tàu nhiều nhất đồng thời tìm kiếm ở băng ~k~.
Sample Input
2 4
1 1 2
1 2 3
Sample Output
2
Nguồn: Thầy Nguyễn Thanh Tùng
Comments