Oyun vaxtı#2104
Vasya yeni bir kompüter oyunu alıb. Oyunda irəliləmək üçün bir neçə tapşırığı yerinə yetirməlidir və hər bir tapşırıq yalnız müəyyən bir əvvəlki tapşırığı tamamladıqdan sonra açılır. Hər bir tapşırığa çatmaq üçün oyunun başlanğıcından həmin tapşırığa qədər unikal bir tapşırıqlar ardıcıllığı mövcuddur.
Həvəsli bir oyunçu olan Vasya yalnız bir gedişi deyil, oyundakı bütün tapşırıqları yerinə yetirmək istəyir. Bunun üçün hər hansı bir sonluğa çatdıqdan sonra oyunu yenidən başlayıb, araşdırılmamış budaqlara gedərək bütün fərqli tapşırıqları başa vurmalıdır.
Ümumi tapşırıq var, tapşırıqlar -dən -ə qədər nömrələnib. Oyun nömrəli tapşırıqdan başlayır. Hər bir tapşırığı yerinə yetirmək T_i dəqiqə çəkir, hətta Vasya həmin tapşırığı əvvəlki gedişdə yerinə yetirmiş olsa belə.
Vasyanın oyundakı bütün tapşırıqları tamamlaması üçün lazım olan minimal vaxtı hesablayın.
Birinci sətirdə bir tam ədəd (1 \leq N \leq 100) verilir.
İkinci sətirdə hər bir tapşırıq üçün vaxt, T_i (1 \leq T_i \leq 100), ardıcıllıqla verilir (1 \leq i \leq N).
Üçüncü sətirdə keçidlərin sayı M = N-1 verilir.
Sonrakı sətrin hər birində iki tam ədəd və verilir, bu isə o deməkdir ki, tapşırığını yalnız tapşırığını tamamladıqdan sonra yerinə yetirmək olar. Bütün -lər fərqlidir.
Tapşırıqlar arası keçid vaxtı və oyunun yenidən başladılması üçün vaxt sıfır hesab olunur.
Vasyanın oyundakı bütün tapşırıqları yerinə yetirməsi üçün lazım olan minimal vaxtı çap edin.
Nümunə 1