Problem
Mèo Ngỗng đã chuẩn bị cho Nick Fury một chiếc bàn hình chữ nhật có kích thước a \(n \cdot m\) chứa các số từ 0< /span> code> thành p−1. Nick Fury ngay lập tức nhận ra rằng mỗi số trong bảng này được chọn ngẫu nhiên với xác suất bằng nhau từ 0 đến p− 1 , bất kể những cái khác.
Nhiệm vụ của bạn — tìm một ma trận con hình chữ nhật của bảng này, trong đó tổng chia hết cho p. Trong số tất cả các ma trận con như vậy, bạn cần tìm một ma trận có tổng các phần tử lớn nhất.
Thông thường, bạn cần tìm
\(1 <= i_1 <= i_2 <= n\),
\( 1 <= j_1 <= j_2 <= m\) tổng của
ax,y trên tất cả
\(i_1 <= x <= i_2\),
\(j_1 <= y <= j_2\) chia trên
p và trong số này có số tiền tối đa.
Đầu vào
Dòng đầu tiên chứa ba số nguyên n, m, p (\(1 < ;= n m, p <= 1.000.000\)) — kích thước của ma trận và số để chia tổng của ma trận con.
Các dòng n sau chứa các số nguyên m, số thứ j trong dòng thứ i bằng ai,j (\(0 <= a_{i,j} <= p ? 1\) ).
Chúng tôi đảm bảo rằng mỗi số trong a được chọn ngẫu nhiên một cách độc lập, có xác suất ngang nhau từ 0 đến p−1.
Đầu ra
In một số nguyên duy nhất — tổng lớn nhất của một ma trận con hình chữ nhật trong đó tổng chia hết cho p. Nếu không có, hãy in 0.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
6 7 5
0 0 3 0 1 0 4
0 2 3 0 2 2 1
2 4 1 4 4 0 3
1 1 0 2 0 3 2
3 0 3 1 0 1 2
1 2 0 0 3 3 1
|
65 |