Dịch chuyển


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Cho một bảng $N$ hàng $M$ cột và một số nguyên $K$. Ô ở hàng thứ $i$ và cột thứ $j$ có giá trị $a_{i,j}$.

Bạn đang ở ô $(1,1)$, bạn cần đến ô $(N,M)$, có thể di chuyển xuống hoặc sang phải.

Trước khi di chuyển, bạn có thể thực hiện một số lần tùy ý thao tác sau: Chọn một hàng $i$ và dịch chuyển các ô hàng $i$ sang trái một ô. Tức là đặt $a_{i,j} = a_{i,(j \ mod \ m)+1}$ với mọi $j \ (1\le j \le m)$.

Gọi $x$ là số lần thực hiện thao tác trên, $y$ là tổng các ô trên đường đi từ $(1,1)$ đến $(N,M)$. Tìm giá trị nhỏ nhất của $kx+y$.

Dữ liệu

  • Dòng đầu tiên chứa ba số nguyên $N,M,K \ (1 \le N,M \le 200; 0 \le K \le 10^9)$;
  • $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên $a_{i,j} \ (0\le a_{i,j} \le 10^9)$;

Kết quả

  • Kết quả bài toán.

Chấm điểm

20; $K=0$. 30; $N,M\le 10$. 50; Không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

input

3 3 100
3 4 9
5 2 4
0 101 101

output

113
Ví dụ 2

input

3 4 1
10 0 0 10
0 0 10 0
10 10 0 10

output

6

Comments

There are no comments at the moment.