T - Örtük
Əgər siz heç vaxt Tetris oynamısınızsa, aşağıdakı kimi bir fiqurla tanış ola bilərsiniz:
Bu fiquru T-tetramino adlandıracağıq. Tetramino - sadəcə 4 hüceyrədən ibarət əlaqəli bir geometrik fiqurun adıdır. Şəkildə göstərilən mərkəzi hüceyrə mərkəzi hüceyrə adlanır.
Manka m sıra və n sütundan ibarət bir düzbucaqlı şəbəkə çəkir və hər bir hüceyrəyə müəyyən bir rəqəm yazır. Cədvəl sıraları 0-dan m - 1-ə qədər, sütunlar isə 0-dan n - 1-ə qədər nömrələnir. O, bəzi hüceyrələri xüsusi olaraq qeyd edir - məsələn, onları qırmızı rəngə boyayır. Daha sonra, o, dostu Nika'dan şəbəkədə bir neçə T-tetramino yerləşdirməsini xahiş edir ki, aşağıdakı şərtlər yerinə yetirilsin:
T-tetramino sayısı xüsusi hüceyrələrin sayı ilə eyni olmalıdır.
Hər bir T-tetramino üçün onun mərkəzi hüceyrəsi xüsusi hüceyrədə olmalıdır.
Heç bir T-tetramino cütü üst-üstə düşməməlidir.
Bütün T-tetramino tamamilə çəkilmiş şəbəkədə yerləşməlidir. Qeyd edək ki, hər bir T-tetramino üçün 4 mümkün yerləşmə mövcuddur.
Əgər şərtlər yerinə yetirilə bilməzsə, Nika No cavabını verməlidir; əgər yerinə yetirilə bilirsə, o, T-tetramino ilə örtülmüş hüceyrələrdəki rəqəmlərin cəmini maksimuma çatdıracaq bir yerləşmə tapmalıdır. Bu halda o, Manka'ya T-tetramino hüceyrələri ilə örtülmüş maksimum cəmi bildirməlidir.Nika'ya bu tapşırığı həll etməkdə kömək edəcək bir proqram yazın.
Giriş Məlumatları
Birinci sətir m və n tam ədədlərini - cədvəlin hündürlüyü və enini ehtiva edir. Növbəti m sətir hər biri n tam ədəd ehtiva edir, 0-dan 1000-ə qədər intervalda. i-ci sıranın j-ci hüceyrəsində yazılmış rəqəmə uyğun olan j-ci tam ədəd.Növbəti sətir k [1,.....,m*n] — cədvəldəki xüsusi hüceyrələrin sayını ehtiva edir. Sonrakı hər bir sətir iki ədəd r[i] və c[i] ehtiva edir, r[i] [0,....,m-1] və c[i] [0,....,n-1] — müvafiq olaraq i-ci xüsusi hüceyrənin sıra və sütun nömrəsi. Bütün xüsusi hüceyrələrin koordinatlarının unikal olduğu təmin edilir.
Çıxış Məlumatları
T-tetramino hüceyrələri ilə örtülmüş rəqəmlərin mümkün maksimum cəmini çıxarın, əgər onları yerləşdirmək üçün bir yol yoxdursa, No çıxarın.
Məhdudiyyətlər
(1 ≤ mn ≤
10^6)
Birinci nümunəyə izah
