Chọn hoa

Điểm: 7,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

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) \cdot 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 \leq t \leq 10 000$
$1 \leq n \leq 10^{9}$
$1 \leq m \leq 10^{5}$
$0 \leq a_{i}, b_{i} \leq 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ụ

Input	Output	Giải thích
2 4 3 5 0 1 4 2 2 5 3 5 2 4 2 3 1	14 16	Bộ 1: chọn $1$ bông loại $1$ và $3$ bông loại $2$ , tổng $= 5 + (1 + 2 \cdot 4) = 14$ . Bộ 2: chọn $2$ bông loại $1$ , $2$ bông loại $2$ , $1$ bông loại $3$ , tổng $= (5 + 2) + (4 + 2) + 3 = 16$ .
1 7 1 107402237 913999333	5591398235	Chỉ có một loại nên phải chọn cả $7$ bông cùng loại: $107402237 + 6 \cdot 913999333 = 5591398235$ .

Bình luận

Không có bình luận tại thời điểm này.