Cerința

John a pornit într-o drumeție. El se află în orașul 1. Se știe efortul pe care îl depune pentru a străbate fiecare oraș, e[i]. De asemenea, se cunoaște și k[i], cu semnificația că orașul i comunică cu orașele care apartin intervalului [max(1, i - k[i]), min(i + k[i], n)]. Observație : Dacă se află în orașul i, acesta poate merge în orașul j doar dacă i comunică cu j și j comunică cu i. Ajutați-l pe John să determine efortul minim pe care trebuie să-l depună pentru a ajunge în orașul n.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi 2 * n numere naturale.

Date de ieșire

Programul va afișa efortul minim pe care îl va depune Hatz John.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• cele 2 * n numere citite sunt naturale, mai mici sau egale cu 1.000.000.000

Exemplu:

Intrare

5
100 1
200 75
300 100
400 25
500 3

Ieșire

800

Explicație

Drumul parcurs de John este 1 -> 2 -> 5.