Dosah

Je dáno M×N uzlů, které jsou uspořádány do čtvercové mřížky obsahující M řádků a N sloupců. Dva uzly mřížky jsou sousední, pokud spolu bezprostředně sousedí buď horizontálně nebo vertikálně, každý uzel mřížky má tak alespoň 2 sousedy a nejvýše 4 sousedy. Každý bod mřížky je buď aktivní nebo neaktivní. Z každého aktivního bodu lze vyslat signál dané celočíselné intenzity I, který putuje mřížkou. Cesta signálu mřížkou vede vždy z některého uzlu do sousedního uzlu, signál nemůže žádné uzly přeskakovat, jinak ale může být cesta signálu zcela libovolná. Pokud signál na své cestě narazí na neaktivní uzel, zaniká. Dále platí také to, že intenzita signálu se o jednotku sníží po každém příchodu do některého aktivního uzlu. V okamžiku, kdy se intenzita signálu sníží na 0, signál zaniká. Dosahem aktivního uzlu U rozumíme počet takových jiných aktivních uzlů mřížky, do nichž může dorazit signál dané intenzity vyslaný z uzlu U.

Množinu M uzlů sítě nazveme souvislou oblastí, pokud se lze z libovolného uzlu U této množiny dostat do libovolného jiného uzlu V této množiny tak, že cesta vedoucí z U do V nikdy v neopustí množinu M. Přitom každý uzel na cestě musí být sousedem bezprostředně předcházejícího/následujícího uzlu na cestě.

Úkolem je zjistit velikost maximální souvislé oblasti obsahující pouze aktivní uzly s maximálním dosahem pro danou počáteční intenzitu I.

Vstup

Na vstupu jsou tři řádky. První řádek obsahuje dvě celá kladná čísla M a N oddělená mezerou, která reprezentují velikost sítě. Platí 1 ≤  M⋅N ≤  10000.
Druhý řádek obsahuje tři kladná celá čísla A, B, C v tomto pořadí, oddělená mezerou. Čísla specifikují, které uzly sítě jsou aktivní. Uzel na řádku r a ve sloupci s je aktivní právě tehdy, když platí
[A⋅r⋅(s+1) + B⋅(r+1)⋅s] mod C ≠  0.
Řádky i sloupce sítě se číslují počínaje 0.
Poslední řádek vstupu obsahuje jediné celé číslo I představující počáteční intenzitu signálu vysílaného z libovolného uzlu sítě.
Je zaručeno, že všechny aktivní uzly sítě tvoří souvislou oblast, tj. to jest signál dostatečné intenzity dosáhne z libovolného aktivního uzlu do jiného libovolného aktivního uzlu.

Výstup

Na výstupu je jediný řádek obsahující dvě celá čísla oddělená mezerou. První představuje maximální hodnotu dosahu, kterou některý uzel sítě může mít při dané počáteční intenzitě I. Druhé číslo představuje počet uzlů maximální souvislé oblasti obsahující pouze aktivní uzly s maximálním dosahem při dané počáteční intenzitě I.

Příklad 1

Vstup: 
6 8
4 1 12
2
Výstup: 
11 4
Pro přehled uvádíme mřížku, kde jsou aktivní resp. neaktivní uzly vyznačeny tečkou resp. křížkem a dále tutéž mřížku s vyznačeným dosahem jednotlivých uzlů. 
  X  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .
  X  .  .  X  .  .  X  .
  .  .  .  .  .  .  .  .
  .  .  X  .  .  .  .  .

  0  6  7  8  8  8  7  5
  5  9 11 10 11 11  9  7
  5 10 11 10 11 11  9  7
  0  9  8  0  9  9  0  6
  5  8  9  8 10 10  8  6
  3  5  0  5  7  8  6  5

Příklad 2

Vstup: 
6 10
5 3 11
1
Výstup: 
4 20
Pro přehled uvádíme mřížku, kde jsou aktivní resp. neaktivní uzly vyznačeny tečkou resp. křížkem a dále tutéž mřížku s vyznačeným dosahem jednotlivých uzlů. 
  X  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  X  .  .
  .  .  .  .  .  .  .  .  X  .
  .  X  .  .  .  .  .  .  .  .
  .  .  .  X  .  .  .  .  .  .

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

Příklad 3

Vstup: 
1000 10
11 50 150
20
Výstup: 
357 20

Příklad 4

Vstup: 
10 10
40 21 150
25
Výstup: 
95 96
Pro přehled uvádíme mřížku, kde jsou aktivní resp. neaktivní uzly vyznačeny tečkou resp. křížkem a dále tutéž mřížku s vyznačeným dosahem jednotlivých uzlů. 
  X  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  X  .  .  .  .
  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .
  .  .  X  .  .  .  .  X  .  .

  0 95 95 95 95 95 95 95 95 95
 95 95 95 95 95  0 95 95 95 95
 95 95 95 95 95 95 95 95 95 95
 95 95 95 95 95 95 95 95 95 95
 95 95 95 95 95 95 95 95 95 95
 95 95 95 95 95 95 95 95 95 95
 95 95 95 95 95 95 95 95 95 95
 95 95 95 95 95 95 95 95 95 95
 95 95 95 95 95 95 95 95 95 95
 95 95  0 95 95 95 95  0 95 95

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data