Detallar#4851
Müəssisə \textit{Avto-2012} dünyaca məşhur avtomobillər üçün mühərriklər istehsal edir. Mühərrik dəqiq olaraq hissədən ibarətdir və bu hissələr -dən -ə qədər nömrələnmişdir. nömrəli hissə isə p_i saniyəyə hazırlanır. \textit{Avto-2012} müəssisəsinin xüsusiyyəti ondan ibarətdir ki, eyni anda yalnız bir mühərrik hissəsi istehsal edilə bilər. Bəzi hissələrin istehsalı üçün əvvəlcədən hazırlanmış digər hissələrin dəsti tələb olunur.
\textit{Avto-2012}-nin baş direktoru müəssisə qarşısında iddialı bir vəzifə qoyub: sərgidə nümayiş etdirmək üçün nömrəli hissəni ən qısa müddətdə istehsal etmək.
Verilən detallar arasındakı istehsal sırası asılılıqlarına görə nömrəli hissəni istehsal etmək üçün lazım olan ən qısa vaxtı tapacaq bir proqram yazın.
Birinci sətrdə (1 \leq n \leq 10^5) ədədləri — p_1, p_2, \ldots, p_n var, bunlar hər bir hissənin istehsal müddətini (saniyələrlə) göstərir.
Növbəti sətrin hər biri hissələrin istehsal xüsusiyyətlərini təsvir edir. -ci sətir nömrəli hissənin istehsal üçün lazım olan hissələrin siyahısını ehtiva edir. Siyahıda təkrarlanan hissə nömrələri yoxdur. Siyahı boş ola bilər — bu halda buna boş sətir uyğun gələcək! Bütün siyahıların uzunluqlarının cəmi -i keçmir.
Məlumdur ki, detalların istehsalında dövri asılılıqlar mövcud deyil.
nömrəli hissənin ən sürətli istehsalı üçün lazımi minimum vaxtı (saniyələrlə) çap edin.
\begin{example}\exmp{4 8 8 72 34
}{19}\end{example}
Nümunə 1
Nümunə 2
Nümunəyə görə ən qısa yol:\begin{itemize}\item , və nömrəli hissələri sırayla istehsal edin,\item sonra nömrəli hissəni istehsal edin.\end{itemize}Cəmi vaxt 7 + 8 + 8 + 4 = 27 olsa da, və hissələri hissəsi hazırlandıqdan sonra paralel istehsal edilə bilər, ona görə də ən uzun zənciri nəzərə almaq lazımdır və nəticədə vaxt 7 + 8 + 4 = 19 olur.