Một quốc gia lưu hành \(N\) mệnh giá tiền xu, trong đó có đồng \(1\) xu, và một loại tiền giấy trị giá \(K\) xu lớn hơn mọi đồng xu. Một nhà sưu tập muốn có một đồng thuộc mỗi mệnh giá. Ông đã có sẵn một số mệnh giá và đang cầm đúng một tờ \(K\) xu.

Cửa hàng bán hàng hóa với mọi mức giá nguyên từ \(1\) đến \(K-1\) xu. Tiền thừa được trả bằng thuật toán tham lam: khi còn phải trả \(A\) xu, cửa hàng chọn đồng có mệnh giá lớn nhất không vượt quá \(A\), đưa đồng đó cho khách, trừ mệnh giá khỏi \(A\), rồi lặp lại đến khi \(A=0\).

Nhà sưu tập mua đúng một món bằng tờ \(K\) xu. Hãy xác định số mệnh giá mới lớn nhất mà ông có thể nhận được, và trong số các món đạt được số lượng ấy, giá món hàng lớn nhất.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(K\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa \(c_i\) và \(d_i\). Giá trị \(c_i\) là mệnh giá đồng xu; \(d_i=1\) nếu nhà sưu tập đã có mệnh giá này, và \(d_i=0\) nếu chưa có. Các mệnh giá tăng nghiêm ngặt:

và \(c_1=1\).

Dữ liệu ra

Dòng đầu in số mệnh giá mới lớn nhất có thể nhận được. Dòng thứ hai in giá lớn nhất của một món hàng khiến tiền thừa chứa đúng số mệnh giá mới lớn nhất đó.

Ràng buộc

• \(1\le N\le 500\,000\).
• \(2\le K\le 1\,000\,000\,000\).
• \(1\le c_i<K\).

Ví dụ

7 25
1 0
2 0
3 1
5 0
10 0
13 0
20 0

3
6