Bố của Sơn có một cửa hàng đá quý hiện đang sở hữu \(n\) viên kim cương, viên kim cương thứ \(i\) có giá trị \(a_{i}\) và có khối lượng \(b_{i}\).

Để chúc mừng sinh nhật của Sơn, bố của cậu mong muốn tạo ra một tác phẩm nghệ thuật có một không hai để tặng cho cậu. Để thực hiện tác phẩm nghệ thuật trên, ông dự định chọn ra \(k\) viên kim cương, sao cho tổng giá trị trên tổng khối lượng là lớn nhất có thể. Nói cách khác, nếu gọi \(s_{a}\) là tổng giá trị, \(s_{b}\) là tổng khối lượng của các viên kim cương được chọn thì ông muốn giá trị \(\frac{S_{a}}{S_{b}}\) là lớn nhất có thể.

Giả sử giá trị lớn nhất trên được biểu diễn dưới dạng phân số tối giản là \(\frac{p}{q}\) thì bạn được yêu cầu đưa ra hai số nguyên \(p\) và \(q\).

Dữ liệu vào:

• Dòng đầu tiên gồm số nguyên dương \(n,\ k\ (k \leq n \leq 50000)\) là tổng số viên kim cương và số viên kim cương cần chọn.

• \(n\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(a_{i}\) và \(b_{i}\) \((a_{i},\ b_{i}\ \leq 10^{6})\) là giá trị và khối lượng của viên kim cương thứ \(i\).

Kết quả:

• In ra hai số nguyên \(p\) và \(q\) với ý nghĩa như trên đề bài.

Ví dụ:

Giải thích:

• Ở ví dụ thứ nhất, cần chọn các viên kim cương 1, 2, 5. Tổng giá trị trên tổng khối lượng là: \(\frac{5 + 7 + 10}{2 + 6 + 4} = \frac{1}{6}\)

• Ở ví dụ thứ hai, cần chọn các viên kim cương 4, 5, 6. Tổng giá trị trên tổng khối lượng là:

\[\frac{4 + 5 + 6}{1 + 1 + 1} = \frac{5}{1}\]

Ràng buộc

• Subtask 1 (20% số điểm): \(n \leq \ 20\)

• Subtask 2 (20% số điểm): \(n \leq \ 100,\ b_{i}\ \leq \ 100\)

• Subtask 3 (60% số điểm): Không có ràng buộc gì thêm