FERMERIS

UŽDUOTIS 

Fermeris turi daug laukų, kurie iš visų pusių apsodinti kiparisų medžiais. Be to, fermeris dar turi siaurų žemės ruožų, kiekviename kurių auga eilė kiparisų. Tarp bet kurių dviejų gretimų kiparisų, nesvarbu, ar jie pasodinti aplink lauką, ar ruože, būtinai auga vienas alyvmedis. Visi kiparisai yra išsidėstę arba aplink laukus, arba ruožuose, o visi alyvmedžiai yra tarp dviejų gretimų kiparisų.

Vieną dieną fermeris susirgo ir pajuto artinantis mirtį. Jis pasišaukė savo vyriausiąjį sūnų ir tarė jam: „Aš dovanosiu tau bet kuriuos Q kiparisų, kuriuos išsirinksi, ir visi alyvmedžiai tarp gretimų tavo pasirinktų kiparisų atiteks tau.“ Sūnus gali pasirinkti bet kokią kiparisų kombinaciją iš bet kurio lauko ar ruožo. Kadangi vyresnėlis mėgsta alyvmedžius, jis norėtų pasirinkti Q kiparisų taip, kad paveldėtų kiek galima daugiau alyvmedžių.

1-as laukas apsodintas 13 kiparisų

2-as laukas apsodintas 4 kiparisais

3-as laukas apsodintas 8 kiparisais

1-ame ruože auga 4 kiparisai

2-ame ruože auga 8 kiparisai

3-ame ruože auga 6 kiparisai

	

1 pav. Kiparisų išdėstymo pavyzdys; alyvmedžiai nepavaizduoti

Tarkime, kad sūnus paveldi Q=17 kiparisų (1 pav.). Norėdamas paveldėti kuo daugiau alyvmedžių, jis turi pasirinkti visus 1-ojo ir 2-ojo laukų kiparisus – tada paveldės 17 alyvmedžių.

Reikia parašyti programą, kuri pagal duotus duomenis apie laukus, ruožus ir paveldėtų kiparisų skaičių, rastų, kiek daugiausiai alyvmedžių gali paveldėti sūnus. 

PRADINIAI DUOMENYS

Pradinių duomenų bylos vardas farmer.in. Pirmos eilutės pradžioje įrašytas sūnaus paveldėtų kiparisų skaičius Q, toliau laukų skaičius M, po to ruožų skaičius K (visi trys duomenys – sveikieji skaičiai). Antroje eilutėje įrašyta M sveikųjų skaičių N1, N2,… NM – kiparisų skaičiai laukuose. Trečioje eilutėje pateikta K sveikųjų skaičių R1, R2,… RK, – kiparisų skaičiai ruožuose.

REZULTATAS

Rezultatų bylos vardas farmer.out. Byloje turi būti viena eilutė, kurioje įrašytas tik vienas sveikasis skaičius: didžiausias alyvmedžių skaičius, kuriuos gali paveldėti sūnus.

PAVYZDYS

farmer.in						farmer.out

17 3 3
13 4 8
4 8 6

17

				

RIBOJIMAI 

0≤Q≤150000, 0≤M≤2000, 0≤K≤2000, 3≤ N1≤150, 3≤N2≤150,… 3≤NM≤150, 2≤ R1≤150, 2≤R2≤150,… 2≤RK ≤150. Bendras kiparisų skaičius laukuose ir ruožuose yra ne mažesnis nei Q. 
50% testų, Q≤1500.