Phân số lớn nhất

Cho hai dãy số $A$ và $B$, mỗi dãy có $N$ phần tử, các phần tử của mỗi dãy số đều là số nguyên dương và có giá trị không lớn hơn ${10}^6$.

Cần tìm giá trị ${\displaystyle \frac{S_A}{S_B}}$ lớn nhất có thể, trong đó $S_A$ là tổng của $K$ phần tử trong $A$, $S_B$ là tổng của $K$ phần tử trong $B$. Lưu ý, nếu đã chọn phần tử $A_i$ thì cũng phải chọn phần tử $B_i$ tương ứng. Nói cách khác, ta chọn $K$ chỉ số đôi một khác nhau $i_1,i_2,\dots ,i_K$, khi đó $S_A=A_{i_1}+A_{i_2}+\dots +A_{i_K}$ và $S_B=B_{i_1}+B_{i_2}+\dots +B_{i_K}$.

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 ${\displaystyle \frac{P}{Q}}$, bạn cần in ra giá trị $P$ và $Q$ này.

Dữ liệu vào

• Dòng đầu tiên ghi hai số nguyên $N$ và $K$ ($1\le K\le N\le 5000$).
• $N$ dòng tiếp theo, dòng thứ $i$ ghi hai số nguyên dương $A_i$ và $B_i$ ($A_i,B_i\le {10}^6$).

Dữ liệu ra

In ra hai số nguyên $P$ và $Q$ (cách nhau một dấu cách) với ý nghĩa như mô tả.

Ràng buộc

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

Ví dụ