Công ty XYZ có \(n\) kho và \(m\) nhân viên làm nhiệm vụ quản lý các kho. Cho biết các thông tin sau:

• Nhân viên thứ \(i\) có năng lực \(1 \le P_i \le 10^6\).
• Các kho đều giống nhau và mỗi kho chỉ do một nhân viên quản lý, nhưng một nhân viên có thể quản lý nhiều kho. Nếu nhân viên \(i\) quản lý \(k\) kho thì độ an toàn của các kho đó là \(S = P_i \text{ div } k\). Nếu một kho không có ai quản lý thì độ an toàn bằng \(0\).
• Độ an toàn của tất cả các kho là \(L\), bằng độ an toàn nhỏ nhất trong \(n\) kho.
• Mỗi tháng công ty sẽ trả lương cho các nhân viên, nếu nhân viên \(i\) được chọn thì sẽ phải trả \(P_i\) dollar. Tổng số tiền phải trả cho các nhân viên được chọn là \(Y\).

Yêu cầu: Chọn và phân công các nhân viên quản lý các kho để độ an toàn của tất cả các kho (\(L\)) là lớn nhất, nếu có nhiều cách phân công thì chọn cách hết ít tiền nhất (\(Y\)).

Input

Gồm nhiều bộ dữ liệu (có không quá \(10\) bộ), mỗi bộ dữ liệu có dạng:

• Dòng 1: gồm 2 số \(n, m\) (\(1 \le n, m \le 300\)).
• Dòng 2: gồm \(m\) số \(P_i\).
• Kết thúc file bằng dòng chứa hai số \(n = m = 0\).

Output

• Gồm nhiều dòng, mỗi dòng gồm 2 số \(L\) và \(Y\) là kết quả tương ứng với dữ liệu vào.

Example

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

3 7
10 10
8 18
0 0

Nguồn: Bài tập thầy Đỗ Đức Đông năm 2019