Počet bodov:
Popis:  15b
Program:  10b

Hurááá! Prázdniny! Povedal si Samko a začal sa tešiť na ničím nerušený oddych. Konečne bude môcť robiť všetko, na čo počas roka nebol čas. Dievčatá, plávanie, opaľovanie sa, dievčatá, ochutnávka kávy, dievčatá, hranie spoločenskej hry, dievčatá, sledovanie obláčikov, učenie sa, spoločenská hra, ochutnávka nemeckých klobás, dievčatá, spánok, spoločenská hra, túra a tak ďalej. Keď má človek ale toľko plánov, musí si ich poriadne naplánovať.

Začal teda rozmýšľať, čo ktorý deň urobí. Nie všetko sa totiž hodí na ľubovoľný deň. Napríklad takého 5.9. určite nie je čas na dievčatá, ale deň po tom je už fajn. Takisto Samko vie, že v jeden deň spraví maximálne jednu vec. Ak by totiž riešil dievčatá, tak na taký spánok mu naozaj čas nezostane.

Prišiel teda s perfektným nápadom. Na každý deň si stanovil štyri (nie nutne rôzne) alternatívy. Potom sa znovu zamyslel a poriadne si spísal, aké veci chce cez prázdniny naozaj stihnúť. Na poradí mu nezáleží, ale ak si raz naplánoval opaľovanie a opaľovanie, tak sa chce naozaj opaľovať dva krát. Je však naozaj možné, aby stihol všetky naplánované aktivity?

Úloha

Prázdniny majú \(n\) dní. Na každý deň má Samko vybrané štyri možné aktivity, z ktorých môže maximálne jednu ten deň vykonávať. Na celé prázdniny má zoznam \(k\) aktivít, ktoré chce stihnúť. Je to ale možné? Koľko najviac toho dokáže absolvovať?

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1\leq n \leq 10\,000\)) udávajúce počet prázdninových dní. Nasleduje \(n\) riadkov so štyrmi číslami \(a_1 , a_2, a_3, a_4 \leq 1\,000\,000\) oddelenými medzerou, predstavujúce možné aktivity na daný deň. V nasledujúcom riadku je číslo \(k\) (\(1 \leq k \leq 10\,000\)) udávajúce počet aktivít, ktoré chce Samko cez prázdniny stihnúť. V nasledujúcom riadku sa nachádza \(k\) kladných čísiel menších ako \(1\,000\,000\), popisujúce jednotlivé aktivity.

Formát výstupu

Vypíšte jedno číslo – najväčší počet aktivít, ktoré môže Samko cez prázdniny naozaj stihnúť.

Príklad

Input:

5
1 2 2 1
2 2 3 4
3 2 6 7
10 3 2 1
10 2 1 5
5
2 10 2 2 2

Output:

5

S výnimkou predposledného dňa sa bude zúčastňovať aktivity číslo \(2\). V predposledný deň sa zúčastní aktivity \(10\).

Input:

5
1 5 2 8
1 2 5 9
1 3 4 6
1 5 1 2
2 1 7 8
5
1 2 3 4 5

Output:

4

Tu sa Samko musí rozhodnúť, či si dá tretí deň aktivitu 3 alebo 4. Jednu z nich určite neabsolvuje.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.