Đá quý

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 (đôi một khác nhau), 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ị ${\displaystyle \frac{S_A}{S_B}}$ là lớn nhất có thể.

Yêu cầu: 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à ${\displaystyle \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 hai số nguyên dương $N,K$ $(K\le N\le 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\le {10}^6)$ là giá trị và khối lượng của viên kim cương thứ $i$.

Dữ liệu ra

In ra hai số nguyên $P$ và $Q$ với ý nghĩa như trên đề bài.

Ràng buộc

• $1\le K\le N\le 50000$.
• $1\le A_i,B_i\le {10}^6$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $N\le 20$.
• Subtask 2 ($20\%$ số điểm): $N\le 100$, $B_i\le 100$.
• Subtask 3 ($60\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ