SPOJ in Armenian

 — Ափսո՛ս,— ասում է,— ընչի՞ սպանեցիք, զոռով մի ձի էի շինել նստել... էնքան պետք է քշեի ո՜ր…

Քաջ Նազար

 Քաջ Նազարի թագավորությունում նորից վագր է հայտնվել և անհանգստացնում է բնակիչներին։ Իհարկե, ոչ ոք չի էլ կասկածում, որ Նազարը առաջվա պես իրեն առաջ կնետի, կհեծնի վագրն ու դրա հախից կգա։ Բայց արի ու տես, որ Նազարը կորել է, և մինչ բոլորը դես ու դեն ընկած նրան են փնտրում, Ուստիանը նախաձեռնությունը վերցնում է իր ձեռքը։

 Ուստիանը պատրաստվում է օղակաձև խարույկ վառել և վագրին առնել թակարդի մեջ։ Այդ նպատակով նա հարակից գյուղերից հավաքել է N հատ խոտի դեզ և օղակաձև դասավորել դրանք թակարդի երկայնքով։ Խոտի դեզերը համարակալված են 1-ից N թվերով՝ ժամացույցի սլաքի պտույտին հակառակ ուղղությամբ։

Այժմ հարկավոր է դեզերի խոտը տարածել ամբողջ օղակի երկայնքով, որպեսզի խարույկը վառելուց հետո փախչելու անցքեր չմնան։ Ուստիանը հաշվել է, որ բավականաչափ բարձր խարույկ ստանալու համար անհրաժեշտ է օղակի երկայնքի յուրաքանչյուր մետրը ծածկել առնվազն 1 կգ չորացրած խոտով։

Ուստիանը նաև գիտի, որ i-րդ դեզը պարունակում է A_i կգ չորացրած խոտ։ Հայտնի են նաև դեզերի միջև եղած հեռավորությունները օղակի երկայնքով․ i-րդ դեզից մինչև i+1-րդ դեզը հեռավորությունը կազմում է L_i մետր (1 ≤ i ≤ N-1), իսկ N-րդ դեզից մինչև 1-ինը L_N  մետր։

 Ուստիանը խոտը տեղափոխելու է իր ավանակի օգնությամբ, որին նա սայլ է կցել  և կարող է անսահմանափակ քանակությամբ խոտ բարձել։ Այնպես որ, հերթական դեզին մոտենալիս Ուստիանը կարող է դեզն ամբողջությամբ բարձել սայլի մեջ։

 Ուստիանը ցանկանում է պարզել, թե արդյոք հնարավո՞ր է որևէ դեզից սկսել շարժվել ժամացույցի սլաքի պտույտին հակառակ ուղղությամբ և առանց ուղղությունը փոխելու կատարել մեկ լրիվ պտույտ ճանապարհին տարածելով չորացրած խոտը (առնվազն 1 կգ ամեն մետրի համար):

Մուտք

Մուտքի առաջին տողում տրված է խոտի դեզերի N քանակը (2 ≤N≤10⁶)։

Երկորդ տողը պարունակում է  A₁,․․․,А_N թվերը (0 ≤ A_i  ≤ 10⁹ )։

Երրորդ տողը պարունակում է  L₁,․․․,L_N թվերը (1 ≤ L_i  ≤ 10⁹ )։

Քանի որ մուտքային ֆայլը բավականին մեծ է, խորհուրդ ենք տալիս օգտագործել C լեզվի մուտքի և ելքի հրամանները։

Ելք

Ելքի միակ տողում հարկավոր է արտածել նվազագույն համարով դեզը, որտեղից կարելի է սկսել պտույտը։ Եթե այդպիսի դեզ գոյություն չունի, արտածել -1:

Օրինակ

Մուտքը.
5
1 4 1 3 5
3 2 2 1 6

Ելքը.
2