Tiệc vui ngân sách

Một nhóm bạn muốn đi chơi ở một số địa điểm trong thành phố nhưng chỉ có ngân sách \(W\). Địa điểm thứ \(i\) có giá vé \(C_i\) và mang lại độ vui \(V_i\). Mỗi địa điểm chỉ ghé tối đa một lần.

Hãy chọn tập địa điểm sao cho tổng giá vé không vượt quá \(W\) và tổng độ vui là lớn nhất. Nếu có nhiều cách đạt độ vui lớn nhất, hãy xét cách có tổng giá vé nhỏ nhất. In ra hai giá trị: tổng giá vé nhỏ nhất đó và tổng độ vui lớn nhất.

Input

Gồm nhiều bộ dữ liệu, mỗi bộ có dạng:

• Một dòng chứa hai số nguyên \(W\) và \(N\) (ngân sách và số địa điểm).
• \(N\) dòng, dòng thứ \(i\) chứa hai số nguyên \(C_i\) và \(V_i\).

Dữ liệu kết thúc bằng một dòng chứa 0 0 (dòng này không phải là một bộ dữ liệu). Số bộ dữ liệu không vượt quá \(100\).

Output

Với mỗi bộ dữ liệu in ra một dòng gồm hai số nguyên cách nhau bởi dấu cách: tổng giá vé nhỏ nhất và tổng độ vui lớn nhất.

Constraints

• \(0 \le W \le 500\)
• \(1 \le N \le 100\)
• \(5 \le C_i \le 25\)
• \(0 \le V_i \le 10\)

Sample Input

30 5
10 4
12 6
9 3
18 9
7 1
20 3
6 2
8 5
15 1
0 0

Sample Output

30 15
14 7

Explanation

Bộ 1 (ngân sách \(30\)): chọn địa điểm 1 và 4 (giá vé \(10+18=28\), độ vui \(13\)) hoặc địa điểm 2 và 4 (giá vé \(30\), độ vui \(15\)); độ vui lớn nhất là \(15\) với tổng giá vé \(30\). Bộ 2 (ngân sách \(20\), ba địa điểm giá \(6,8,15\)): chọn hai địa điểm đầu, giá vé \(14\), độ vui \(7\).