Fermer#2127
Fermer bir neçə sahəyə malikdir, hər biri sərhədində sərv ağacları əkilib, həmçinin bir neçə zolağa sahibdir, onların hər birində bir sıra sərv ağacları düzülüb. Hər iki ardıcıl sərv ağacı arasında, istər sahə sərhədlərində, istərsə də zolaqlarda, bir zeytun ağacı böyüyür. Bütün fermerin sərv ağacları ya sahə sərhədlərində, ya da zolaqlardadır, bütün zeytun ağacları isə yalnız bu sərhədlərdə və ya zolaqlardakı qonşu sərv ağacları arasındakı yerlərdə yerləşir.
Bir gün fermer ağır xəstələndi və ölümünün yaxınlaşdığını hiss etdi. Ölümündən bir neçə gün əvvəl böyük oğlunu yanına çağırıb dedi: "Sənə istədiyin istənilən Q sərv ağacını və seçdiyin hər iki ardıcıl sərv ağacı arasında böyüyən bütün zeytun ağaclarını miras qoyuram." Hər bir sahədən və zolaqdan oğul istədiyi sərv ağaclarını istədiyi ardıcıllıqla seçə bilər. Oğul zeytun ağaclarına xüsusi maraq göstərdiyindən elə sərv ağacı seçmək istəyir ki, əldə edə biləcəyi zeytun ağaclarının sayı maksimum olsun.
1-ci zolaqda sərv ağacı var
2-ci zolaqda sərv ağacı var
3-cü zolaqda sərv ağacı var
Şəkil . Sərv ağaclarının yerləşməsi nümunəsi
(zeytun ağacları göstərilməyib)
Tutaq ki, oğul Şəkil 1-də göstərilən sahələr və zolaqlar üçün \textbf{Q}=17 sərv ağacı əldə edir. Əldə edilən zeytun ağaclarının sayını maksimum etmək üçün o, 1-ci və 2-ci sahələrdəki bütün sərv ağaclarını seçməlidir və beləliklə zeytun ağacı əldə edir.
Sizdən tələb olunur ki, sahələr, zolaqlar və oğulun seçəcəyi sərv ağaclarının sayı haqqında verilmiş məlumatlara əsasən, oğulun maksimum neçə zeytun ağacını miras ala biləcəyini hesablayan proqram yazasınız.
Girişin ilk sətrində üç tam ədəd verilir: (0 \leq \textbf{Q} \leq 150\,000) — oğulun seçməli olduğu sərv ağaclarının sayı, (0 \leq \textbf{M} \leq 2\,000) — sahələrin sayı və (0 \leq \textbf{K} \leq 2\,000) — zolaqların sayı.
İkinci sətrdə tam ədəd \textbf{N}_1, \textbf{N}_2, \ldots, \textbf{N}_M (3 \leq \textbf{N}_1 \leq 150, 3 \leq \textbf{N}_2 \leq 150, , 3 \leq \textbf{N}_M \leq 150) — sahələrdəki sərv ağaclarının sayı verilib.
Üçüncü sətrdə tam ədəd \textbf{R}_1, \textbf{R}_2, \ldots, \textbf{R}_K (2 \leq \textbf{R}_1 \leq 150, 2 \leq \textbf{R}_2 \leq 150, , 2 \leq \textbf{R}_K \leq 150) — zolaqlardakı sərv ağaclarının sayı verilib.
Çıxışda bir tam ədəd olmalıdır — oğulun miras ala biləcəyi maksimum mümkün zeytun ağaclarının sayı.
Nümunə 1