Xoay cột

Điểm: 7,00 (OI)

Giới hạn thời gian: 3.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

Cho một ma trận $n \times m$ gồm các số nguyên dương $a_{i, j}$ .

Trong một thao tác, bạn có thể chọn một cột bất kỳ và dịch vòng các phần tử trong cột đó (phần tử ở hàng cuối quay lên hàng đầu, các phần tử còn lại dịch xuống một hàng). Bạn được phép thực hiện thao tác này bao nhiêu lần tuỳ ý (kể cả không thực hiện) và có thể dịch một cột nhiều lần.

Sau khi đã hoàn tất các thao tác dịch, với mỗi hàng $i$ , gọi $r_{i}$ là giá trị lớn nhất trên hàng đó của ma trận thu được. Hãy tìm giá trị lớn nhất có thể của tổng $r_{1} + r_{2} + \dots + r_{n}$ .

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ( $1 \leq t \leq 40$ ) — số bộ dữ liệu.
Với mỗi bộ:
- Dòng đầu chứa hai số nguyên $n$ và $m$ ( $1 \leq n \leq 4$ , $1 \leq m \leq 100$ ).
- $n$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên $a_{i, j}$ ( $1 \leq a_{i, j} \leq 10^{5}$ ).

Dữ liệu ra

In ra $t$ số nguyên trên $t$ dòng — đáp án cho mỗi bộ dữ liệu, theo thứ tự nhập.

Ràng buộc

$1 \leq t \leq 40$
$1 \leq n \leq 4$
$1 \leq m \leq 100$
$1 \leq a_{i, j} \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
2 2 3 2 5 7 4 2 4 3 6 4 1 5 2 10 4 8 6 6 4 9 10 5 4 9 5 8 7	12 29	Bộ 1: dịch cột 3 xuống một hàng, ma trận thành 2 5 4 / 4 2 7. Khi đó $r_{1} = 5$ , $r_{2} = 7$ , tổng $= 12$ . Bộ 2: không cần dịch, $r_{1} = r_{2} = 10$ , $r_{3} = 9$ , tổng $= 29$ .
1 4 3 1 1 100 1 3 1 2 100 100 1 3 1	302	Có thể dịch để mỗi hàng đều "nhận" được một giá trị lớn (gồm hai số 100 ở cột 2/3 và số 100, 2 phân bố hợp lý), đạt tổng $302$ .

Bình luận

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