Sau khi lấy được kho báu, Cuội và nhóm bạn của mình quyết định tổ chức một bữa Party đến các địa điểm vui chơi trong thành phố để ăn mừng. Tuy nhiên Cuội chỉ mang theo ngân sách là $W$, Cuội muốn đạt được niềm vui tối đa nhưng chi tiêu không vượt quá giới hạn ngân sách.

Cuội hỏi trước về phí vào cửa cho $N$ địa điểm: Địa điểm thứ $i$ có phí vào cửa là $C_i$ và ước lượng niềm vui đạt được ở đây là $V_i$. Nhưng làm thế nào để Cuội thực sự chọn các bữa tiệc mang lại cho Cuội và nhóm bạn nhiều niềm vui nhất và không vượt quá ngân sách?

Viết một chương trình chọn một số điểm đến sao cho mang lại nhiều niềm vui nhất nhưng chi tiêu không vượt quá ngân sách Cuội có. Hãy nhớ rằng Cuội không nhất thiết phải chi tiêu số tiền chính xác bằng ngân sách Cuội có. Đạt được mức độ vui vẻ cao nhất có thể, và không tiêu nhiều tiền hơn cần thiết.

Dữ liệu vào

• Dòng đầu tiên của đầu vào chỉ định ngân sách bạn có $W$ và số địa điểm là $N$.
• $N$ dòng sau chứa hai số. Số đầu tiên cho biết phí vào cửa, số thứ hai cho biết số lượng niềm vui khi vào địa điểm này.
• Có nhiều trường hợp thử nghiệm. Đầu vào kết thúc bằng $00$.

Dữ liệu ra

• Đối với mỗi trường hợp thử nghiệm, chương trình của bạn phải xuất tổng của phí vào cửa nhỏ nhất và tổng niềm vui lớn nhất của một giải pháp tối ưu. Cả hai số phải được phân tách bằng một khoảng trắng.

Ràng buộc

• $1\le N\le 100$
• $0\le W\le 500$
• $5\le C\le 25$
• $0\le V_i\le 10$

Input 1

50 10
13 8
19 10
16 8
12 9
10 2
12 8
13 5
15 5
11 7
16 2
0 0

Output 1

48 32