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