Kübik#3926

Kübik

5 saniyə
256 meqabayt
Çox asan

Son zamanlar masa oyunları çox populyar olub. Həm bir vaxtlar unudulmuş, həm də yeni maraqlı oyunlar həyatımıza geri qayıdır. Sizə tamamilə yeni, unikal bir masa oyunu təqdim olunub. Bu oyun üçün bir oyun zarı (onun açılımı şəkildə göstərilib) və hüceyrələrə bölünmüş düzbucaqlı oyun sahəsi lazımdır. Sahənin hər bir hüceyrəsində tam ədəd yazılıb.

Oyun aşağıdakı qaydalarla bir neçə nəfər tərəfindən oynana bilər:

  1. İlk gedişdə oyunçu zarı sahənin sol üst hüceyrəsinə istənilən tərəfi ilə qoyur.

  2. Hər növbəti gedişdə oyunçu sağda və ya aşağıda olan qonşu hüceyrəyə keçərək zarı 4 qonşu tərəfdən birinə çevirir.

  3. Hər gediş üçün oyunçu K·A xal alır, burada A - sahənin cari hüceyrəsində yazılmış ədəd, K - zarı oyun sahəsində dayanan tərəfin üzərindəki rəqəmdir.

  4. Oyunçu sağ alt hüceyrəyə çatana qədər gedir. Sonra onun bütün gedişləri üçün xallar toplanır.

  5. Bir oyunçu gedişini bitirdikdən sonra ikinci oyunçu başlayır və s.

  6. Qalib - ən çox xal toplayan oyunçudur.

Verilmiş oyun sahəsinə görə, göstərilən qaydalarla oynayaraq əldə edilə biləcək maksimum xal məbləğini müəyyən edin.

Giriş

Giriş faylının ilk sətiri T - testlərin sayını (T ≤ 200) ehtiva edir. Hər testin ilk sətiri boşluqla ayrılmış N və M ədədlərini - oyun sahəsinin ölçülərini (1 ≤ N·M ≤ 10^5) ehtiva edir. Daha sonra N sətir boyunca M ədədlər, boşluqla ayrılmış - oyun sahəsinin hüceyrələrində yazılmış ədədlər gəlir. Bütün ədədlər modul üzrə 10^3-dən çox deyil.

Çıxış

Hər test üçün ayrı sətirdə bir tam ədəd çıxarın - optimal oyunla əldə edilə biləcək maksimum xal miqdarı.

Nümunələr

Nümunə 1

Loading
Loading