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ị ~\dfrac{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à ~\dfrac{P}{Q}~ thì bạn được yêu cầu đưa ra hai số nguyên ~P~ và ~Q~.

Input

• Dòng đầu tiên gồm 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~.

Output

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

Scoring

Sample Input 1

5 3
5 2
7 6
8 9
1 4
10 4

Sample Output 1

11 6

Sample Input 2

6 3
1 1
2 1
3 1
4 1
5 1
6 1

Sample Output 2

5 1

Notes

• Ở 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à:

  ~\dfrac{5 + 7 + 10}{2 + 6 + 4} = \dfrac{11}{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à:

  ~\dfrac{4 + 5 + 6}{1 + 1 + 1} = \dfrac{5}{1}~.