Domácí kolo

H: Apokalypsa

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

Zadání

Píše se rok 2077 a globální oteplování vyhnalo všechny přeživší do posledních dvou měst na zemských pólech, kde lze ještě pořád pěstovat některé odolnější plodiny. Některé suroviny jsou bohužel dostupné pouze na jednom z pólů, a tak jsou na sobě obě města závislá. Suroviny se přepravují transportéry, které umí plout po vodě i jezdit po pevnině. Kam ale transportéry nemůžou, jsou pouště, protože ty jsou kvůli globálnímu oteplování tak teplé, že by tam řidič transportéru moc dlouho nepřežil.

Nedávno lidé zalesnili všechny pouště, a tak mohou transportéry v tuto chvíli jezdit všude. Země se stále otepluje, a tak každý den vznikne nová poušť. Kdyby takováto poušť měla zabránit transportérům dostat se z jednoho pólu na druhý, tak se obě města dohodnou a vzniku pouště zabrání (a na tomto políčku může v budoucnu vzniknout poušť znovu). Stojí je to ale 1 bžilion.

Vědci už umí předpovědět, kde budou pouště vznikat. Teď se snaží spočítat, kolika nově vzniklým pouštím budou muset zabránit, aby se mezi městy stále mohli přepravovat. Lidé jsou líní, a byť znají předpověď, tak budou bránit vzniku pouští jen pokud by vznikem pouště zanikla poslední cesta mezi městy. (Dokonce jsou líní i tehdy, pokud by mohli zabráněním vzniku pouště, která neničí poslední cestu, ve výsledku ušetřit.)

V městských pokladnách je teď N bžilionů peněz. Lidé přemýšlí, kolik peněz si musí v pokladně nechat, aby zvládli udržovat cestu mezi městy dalších N dní a kolik mohou investovat do ostatních aktivit.

Zemi reprezentujeme jako mřížku, kde s celou spodní hranou sousedí jedno město a celou s horní hranou město druhé. Zemi lze obejít kolem dokola, a tak je pravá strana mřížky spojená s levou stranou. Transportéry se mohou přesouvat mezi políčky jenž sousedí přes hranu.

Tvar vstupu

Na prvním řádku vstupního souboru je číslo T, počet problémů, které musíte vyřešit.

Pro každý problém dostanete na prvním řádku čísla R, C a N, kde R je počet řádků, C počet sloupečků a N počet dní, kdy budou vznikat pouště a počet bžilionů v městských pokladnách.

Následuje N řádek s jednotlivými předpovědmi vzniku pouště ve formátu r\; c, které říkají, že vznikne nová poušť na souřadnicích [r, c], kde 1 \leq r \leq R a 1 \leq c \leq C.

Teď si můžeme trochu formálněji říci jak se transportéry mohou pohybovat. Transportéry se mohou přesunout mezi políčky [r_1, c_1] a [r_2, c_2], pokud platí alespoň jedno z následujících:

  • c_1 = c_2 a |r_1 - r_2| = 1 - políčka jsou vedle sebe vertikálně
  • r_1 = r_2 a |c_1 - c_2| = 1 - políčka jsou vedle sebe horizontálně
  • r_1 = r_2 a c_1 = 1 a c_2 = C - mohou chodit přes boční okraj mřížky jedním směrem
  • r_1 = r_2 a c_1 = C a c_2 = 1 - mohou chodit přes boční okraj mřížky druhým směrem

Tvar výstupu

Pro každý problém vypište jeden řádek s jedním číslem, a to kolik bžilionů mohou lidé investovat, aby jim zbylo dost peněz na udržení cesty mezi městy.

Lehká verze

  • 1 \leq T \leq 100
  • 1 \leq R, C \leq 4000
  • R \leq N \leq 5 \cdot 10^5
  • Součet hodnot N přes všechny problémy je nejvýše 3 \cdot 10 ^ 6.
  • Prvních R-1 pouští bude vznikat na souřadnicích [1, 1], [2, 1], \dots, [R-1, 1].

Těžká verze

  • 1 \leq T \leq 100
  • 1 \leq R, C \leq 4000
  • 0 \leq N \leq 5 \cdot 10^5
  • Součet hodnot N přes všechny problémy je nejvýše 3 \cdot 10 ^ 6.

Ukázkový vstup

2
3 4 9
2 2
3 2
2 3
3 4
3 1
1 3
2 1
1 1
1 4
3 4 9
1 1
2 1
2 2
3 2
2 3
3 4
3 1
1 3
1 4

Ukázkový výstup

6
7

Vysvětlení ukázkového vstupu a výstupu

U prvního vstupu lidé zabrání vzniku pouští na políčkách [3, 1], [2, 1] a [1, 4] (znázorněno na obrázku).

V případě druhého vstupu se zabrání vzniku pouští na políčkách [3, 4] a [1, 4].

První problém by se mohl vyskytnout jen v těžké variantě vstupu a druhý v obou.

Máš na to!

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