Nanoroboty shromažďují vzorky

Zadání

Pokusné obdélníkové pole je rozděleno do M × N čtvercových sektorů. V každém sektoru je umístěno několik vzorků. Pokusné nanoroboty, které mají za úkol vzorky shromažďovat, pracují v poli podle pravidel uvedených dále.

Každý nanorobot má určen startovní a koncový sektor. Koncový sektor vždy leží buď ve stejném řádku nebo ve stejném sloupci jako startovní sektor. Úkolem nanorobota je projít všemi sektory na přímé dráze ze startovního do koncového sektoru a shromaždit všechny vzorky ve všech navštívených sektorech. Když nanorobot shromáždí vzorky ve svém cílovém sektoru, zastaví se a nepokračuje v žádné činnosti. Je zaručeno, že jakmile nanorobot začne pracovat v určitém sektoru, shromáždí v něm všechny vzorky.

Činnost kteréhokoli nanorobota v kterémkoli sektoru kontaminuje prostředí sektoru natolik, že když do sektoru navštíveného dříve jedním nanorobotem vstoupí další nanorobot, ztrácí tento druhý nanorobot orientaci, zastaví se a už nepokračuje v pohybu a shromažďování dalších vzorků.

Nanoroboty jsou do svých startovních sektorů umisťovány jeden po druhém. Další nanorobot je do svého startovního sektoru umístěn až poté, co se předchozí nanorobot zastaví. Nezáleží přitom, zda se předchozí nanorobot zastavil po shromáždění vzorků ve svém koncovém sektoru nebo po vstupu do některého kontaminovaného sektoru. Pokud nanorobot kontaminuje svou činností startovní pole jiného nanorobota, který bude umístěn do pole později, nevykoná tento další nanorobot již žádnou činnost a neshromáždí žádné vzorky.

Experimentátoři chtějí nanoroboty do pole umisťovat v takovém pořadí, aby maximalizovali celkový počet vzorků shromážděných všemi nanoroboty.

Obrázek 1. Obrázek odpovídá situaci z Příkladu 1 níže. V pravém dolním rohu každého ze 36 sektorů je vepsán počet vzorků, které se v něm původně nacházejí. V levém schématu je přerušovanými čarami znázorněna možná dráha každého nanorobota z jeho startovního sektoru do jeho cílového sektoru. Nanoroboty jsou označeny čísly 0,1, 2, 3. V pravém schématu jsou plnými čarami znázorněny dráhy nanorobotů pro každé pořadí, ve kterém nanoroboty 0 a 1 budou umístěny do pole až po nanorobotu 3. Všechny navštívené sektory jsou zvýrazněny žlutě, celkový počet shromážděných vzorků z těchto sektorů je 54 a je maximální možný. (Černé body představují vstup nanorobotů 0 a 1 do sektoru kontaminovaného nanorobotem 3.)

Úloha

Je znám počet vzorků v každém sektoru pole a je znám startovní a koncový sektor každého robota. Určete maximální možný celkový počet vzorků, které mohou nanoroboty shromáždit, pokud budou do pole umisťovány ve vhodném pořadí.

Vstup

První řádek vstupu obsahuje dvě celá čísla M, N oddělená mezerou a určující počet sektorů podél vertikální a horizontální hrany pole. Předpokládáme, že souřadnice jednotlivých sektorů jsou určeny jejich vertikání a horizontální vzdáleností (v tomto pořadí) od sektoru v levém horním rohu pole, který má souřadnice (0, 0). Následuje M řádků, každý s N hodnotami, určujícími počet vzorků v jednotlivých sektorech. Pokud bychom tyto řádky vstupu indexovali od 0 a hodnoty na každém řádku indexovali rovněž od 0, pak by j-tá hodnota v i-tém řádku představovala počet vzorků v sektoru se souřadnicemi (i, j). Dále je na vstupu řádek s jediným číslem R představujícím počet nanorobotů. Následuje R řádků, každý obsahuje čtyři čísla a, b, c, d oddělená mezerou a popisující startovní a cílový sektor jednoho z nanorobotů. Startovní sektor má souřadnice (a, b), cílový sektor má souřadnice (c, d), kde a = c nebo b = d.

Platí 2 ≤ M, N ≤ 50, 2 ≤ R ≤ 10, počet vzorků v jednom sektoru je nejvýše 1000.

Výstup

Na výstupu je jeden textový řádek s jedním číslem představujícím maximální možný celkový počet vzorků, které mohou nanoroboty shromáždit, když budou do pole umisťovány v co nejvýhodnějším pořadí.

Příklady

Příklad 1

Vstup

6 6
1 1 1 9 1 1
3 5 2 1 2 1
1 1 1 9 1 1
1 1 1 2 1 1
1 9 3 1 3 1
1 1 1 9 1 1
4
4 4 4 1
1 5 1 0
5 1 1 1
5 3 0 3

Výstup

Schémata ilustrující situaci a řešení Příkladu 1 jsou znázorněna na Obrázku 1.

Příklad 2

Vstup

4 5
10 10 50 10 90
10 10 40 90 10
20 30 60 50 20
10 10 80 90 90
2
2 0 2 4
0 2 3 2

Výstup

Příklad 3

Vstup

2 9
1 3 4 5 3 1 2 1 9
5 3 4 5 3 7 7 2 1
5
0 1 1 1
0 2 1 2
0 3 1 3
0 4 1 4
1 1 1 7

Výstup

Veřejná data

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