Chọn hoa

Bạn cần chọn đúng $n$ bông hoa từ một cửa hàng có $m$ loại hoa (mỗi loại có vô hạn bông).

Với loại hoa thứ $i$, bông đầu tiên đem lại độ vui $a_i$, và mỗi bông tiếp theo (cùng loại) đem lại độ vui $b_i$. Nói cách khác, nếu trong số $n$ bông hoa được chọn có $x_i>0$ bông loại $i$ thì loại đó đóng góp $a_i+(x_i-1)·b_i$ vào tổng độ vui. Loại không được chọn ($x_i=0$) không đóng góp gì.

Hãy chọn đúng $n$ bông hoa sao cho tổng độ vui đạt giá trị lớn nhất có thể.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $t$ — số bộ kiểm tra.
• Với mỗi bộ:
  • Dòng đầu chứa hai số nguyên $n$ và $m$.
  • $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$.
• Các bộ kiểm tra được cách nhau bởi một dòng trống.

Dữ liệu ra

Với mỗi bộ kiểm tra, in trên một dòng tổng độ vui lớn nhất có thể.

Ràng buộc

• $1\le t\le 10000$
• $1\le n\le {10}^9$
• $1\le m\le {10}^5$
• $0\le a_i,b_i\le {10}^9$
• Tổng $m$ trên toàn bộ các bộ kiểm tra không vượt quá ${10}^5$.

Ví dụ