Oyun vaxtı
Vasya yeni bir kompüter oyunu alıb. Oyunda irəliləmək üçün bir neçə missiyanı yerinə yetirmək lazımdır və hər növbəti missiya, əvvəlki missiyanın nəticəsinə əsaslanır. Hər bir missiyaya çatmaq üçün oyunun əvvəlindən keçilməli olan yeganə missiyalar ardıcıllığı mövcuddur.
Vasya əsl "gamer" olduğu üçün oyunu yalnız başdan sona qədər keçmək istəmir, o, oyundakı bütün missiyaları tamamlamaya qərar verib. Bunun üçün oyunun sonuna çatdıqdan sonra oyunu yenidən başlamaq və daha əvvəl keçmədiyi süjet qolları ilə davam etmək məcburiyyətindədir.
Oyunda ümumilikdə N missiya var və bunlar 1 -dən N -ə qədər nömrələnib. Oyun 1 nömrəli missiyadan başlayır. Hər bir missiya Vasya üçün T_i dəqiqə çəkir, hətta o, bu missiyanı əvvəlki oyun seanslarında keçmiş olsa belə. Vasyaya oyundakı bütün missiyaları keçmək üçün minimum neçə dəqiqə lazım olduğunu hesablayın.
Giriş verilənləri
Girişin birinci sətirində tam ədəd N (1 ≤ N ≤ 100) verilir. İkinci sətirdə hər bir missiyanın keçmə vaxtı boşluqla ayrılmış şəkildə verilib (1 ≤ T_i ≤ 100) ardıcıllıqla (1 ≤ i ≤ N). Üçüncü sətirdə tam ədəd M = (N – 1) — missiyalar arasında keçidlərin sayı verilir. Missiyalar arasında keçid vaxtı və oyunun yenidən başlama vaxtı sıfır hesab edilir. Növbəti M sətirdə hər biri iki ədəd — F və T verilib, bu da T missiyasına yalnız F missiyasını yerinə yetirdikdən sonra keçilə biləcəyini göstərir. Bütün T dəyərləri fərqlidir.
Çıxış verilənləri
Vasyanın oyundakı bütün missiyaları keçməsi üçün lazım olan minimum vaxtı çıxarın.