Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BGMAGIC - MAGIC

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/bgmagic


Đại Ca Đi Học rất thích chơi với các bảng số. Lần này, Đại Ca có một bảng kích thước  n×m. Mỗi ô của bảng có 1 số nguyên dương. Bảng là đẹp nếu các số trong mỗi cột sắp xếp theo thứ tự tăng nghiêm ngặt từ trên xuống dưới, và các số trong mỗi hàng phải xếp theo thứ tự tăng nghiêm ngặt từ trái qua phải. Ví dụ

1 2 3 4

3 4 5 6

5 6 7 8

7 8 9 10

Bảng Siêu đẹp là bảng đẹp, nhưng các số ở 2 ô chéo nhau bất kỳ (2 ô có chung nhau đúng 1 đỉnh) phải khác tính chẵn lẻ. Bảng sau là bảng đẹp, nhưng không phải bảng siêu đẹp

1 2

4 6

Chú ý bảng 4x4 bên trên là bảng Siêu Đẹp.

Cho một bảng số khuyết 1 số ô, hãy giúp Đại Ca Đi Học điền các số vào tất cả các ô khuyết, để bảng trở thành bảng Siêu Đẹp và tổng tất các số trong bảng là nhỏ nhất có  thể.

Input

  • Dòng đầu ghi 2 số n và m (1 ≤ n, m ≤ 2000) là kích thước bảng.
  • Sau đó là n dòng, mỗi dòng ghi m số nguyên c (0 ≤ c ≤ 2000). Ô có số 0 là ô trống cần điền số vào. Số được điền có thể giống nhau, không bị giới hạn ≤ 2000.

Output

  • In ra tổng các ô bé nhất sau khi điền vào các ô trống để tạo ra bảng siêu đẹp. In ra -1 nếu không thể điền để tạo thành bảng siêu đẹp

Example

Input:
4 4
1 2 3 0
0 0 5 6
0 4 7 8
7 0 0 10

Output:
-1
Input:
4 4
1 2 3 0
0 0 5 6
0 0 7 8
7 0 0 10

Output:
88

Được gửi lên bởi:VOJ Team
Ngày:2015-12-09
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:Bắc Giang PreVOI 2015

hide comments
2018-12-24 14:35:13
Tham khảo thuật toán tại https://bit.ly/1QfizKi
2018-10-15 09:27:00
@trungore
bạn nào không làm được thì ib đây nhé :https://www.facebook.com/trungore
2017-12-02 03:53:12
bài này như Kặc. Nộp mãi đéo AC. Tao code 2^n chắc chắn k bị tle!!!
2017-12-02 03:52:31
trâu cg AC :))
2017-12-01 08:05:02
cout << -1 được 43 điểm :v
2015-12-25 05:16:08 The Flash
bài này vẫn dùng đệ qui được cơ mà chú ý là chỉ thử 2 số thôi vì nó phụ thuộc tính chẵn lẻ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.