Verkefni

JOI-þjóðvegurinn liggur beint í austur og vestur, og meðfram JOI-þjóðveginum eru $n$ áningarbæir. Áningarbæirnir eru númeraðir $1, 2, \dots, n$ í röð frá vestri til austurs. Áningarbær $1$ er vestasti áningarbærinn og áningarbær $n$ er austasti áningarbærinn.

Herra JOI leggur af stað frá áningarbæ $1$ í $m$ daga ferðalag. Hann ákveður ferðaáætlun sína samkvæmt rununni $a_1, a_2, \dots, a_m$. Hér er $a_i$ heiltala frábrugðin núlli sem táknar ferðamáta á degi $i$. Nánar tiltekið, ef herra JOI leggur af stað frá áningarbæ $k$ á degi $i$, þá ferðast hann beint frá áningarbæ $k$ til áningarbæjar $k + a_i$ á degi $i$.

Gefið er fjöldi áningarbæja $n$, fjöldi ferðadaga $m$, upplýsingar um vegalengdir milli samliggjandi áningarbæja og runan $a_1, a_2, \dots, a_m$ sem táknar ferðamátana. Skrifið forrit sem finnur afganginn þegar heildarvegalengd herra JOI á þessu $m$ daga ferðalagi er deilt með $100000 = 10^5$.

Inntak

Lesið inntakið úr skránni input.txt.

Á línu $1$ í inntakinu eru tvær heiltölur $n, m$ ($2 \le n \le 100000 = 10^5$, $1 \le m \le 100000 = 10^5$) aðskildar með bili, sem tákna fjölda áningarbæja $n$ og fjölda ferðadaga $m$.

Á næstu $n - 1$ línum eru vegalengdir milli samliggjandi áningarbæja. Á línu $i + 1$ ($1 \le i \le n - 1$) er jákvæð heiltala $s_i$ ($1 \le s_i \le 100$) sem táknar vegalengdina milli áningarbæjar $i$ og áningarbæjar $i + 1$.

Á næstu $m$ línum eru upplýsingar um ferðamátana. Á línu $i + n$ ($1 \le i \le m$) er heiltala frábrugðin núlli $a_i$ sem táknar ferðamátann á degi $i$. Aldrei er farið vestur fyrir áningarbæ $1$ né austur fyrir áningarbæ $n$.

Í $50\%$ prófunargagna gildir $n \le 100$ og $m \le 100$.

Úttak

Skrifið úttakið í skrána output.txt.

Úttakið samanstendur af $1$ línu sem inniheldur afganginn þegar heildarvegalengd herra JOI á þessu $m$ daga ferðalagi er deilt með $100000 = 10^5$.

Dæmi 1

Inntak

7 5
2
1
1
3
2
1
2
-1
3
2
-3

Úttak

18

Skýring

Á degi $1$ ferðast hann frá áningarbæ $1$ til áningarbæjar $3$. Á degi $2$ ferðast hann frá áningarbæ $3$ til áningarbæjar $2$. Á degi $3$ ferðast hann frá áningarbæ $2$ til áningarbæjar $5$. Á degi $4$ ferðast hann frá áningarbæ $5$ til áningarbæjar $7$. Á degi $5$ ferðast hann frá áningarbæ $7$ til áningarbæjar $4$. Heildarvegalengdin á þessu $5$ daga ferðalagi er $18$.