Finále

F: Popeláři

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Popeláři v jednom dalekém městě to nemají vůbec jednoduché. Jsou tam totiž skoro samé jednosměrné ulice, to nejhorší, co vás může potkat, když chcete objet všechny domy a vyvézt odpadky.

Ulice tvoří pravidelnou mřížku R ⨯ S. Popeláři začínají v levém horním rohu. Jednosměrné ulice vedou jen dolů a doprava, ale na K určených křižovatkách se může jet i nahoru a dolů.

Na každé křižovatce města stojí aij popelnic. Určete, kolik nejvíce popelnic mohou popeláři odvézt při jedné projížďce městem.

Tvar vstupu

Na prvním řádku vstupu máte číslo T, počet vstupů ve vstupním souboru.

Na druhém řádku jsou čísla R, S a K. R je počet řádků mapy města, S počet sloupců, K počet křižovatek, na kterých se smí jet všemi směry.

Na dalších R řádcích máte vždy S čísel, to jsou počty popelnic na jednotlivých křižovatkách.

Na dalších K řádcích jsou dvojice r, s. To jsou souřadnice čtyřsměrných křižovatek, znamená to, že se nachází v r-tém řádku a s-tém sloupci. Levý horní roh má souřadnice [0,0], políčko napravo od něj [0,1].

Tvar vstupu

Do výstupního souboru vypište na samostatný řádek jedno celé číslo, počet popelnic, které se z města dají odvézt na jednu návštěvu.

Lehká verze

  • T ≤ 50
  • R,S ≤ 4
  • 0 ≤ K ≤ R · S

Těžká verze

  • T ≤ 20
  • R,S ≤ 300
  • 0 ≤ K ≤ R · S

Ukázkový vstup

2
3 4 0
1 1 1 1
0 2 0 1
0 1 2 0
4 4 4
1 1 1 1
3 2 1 0
1 2 1 2
3 2 1 0
1 1
1 2
2 2
3 0

Ukázkový výstup

7
19

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)