Для участ­ни­ков ве­ло­гон­ки на каж­дом ки­ло­мет­ре коль­це­вой трас­сы с дву­сто­рон­ним дви­же­ни­ем уста­нов­ле­ны пунк­ты пи­та­ния. Длина коль­це­вой трас­сы равна N ки­ло­мет­ров. Ну­ле­вой и N-⁠й ки­ло­мет­ры трас­сы на­хо­дят­ся в одной точке. Из­вест­но ко­ли­че­ство ком­плек­тов пи­та­ния в каж­дом из пунк­тов на трас­се. В каж­дый пункт ком­плек­ты пи­та­ния до­став­ля­ет от­дель­ный элек­тро­кар. Сто­и­мость до­став­ки пи­та­ния вы­чис­ля­ет­ся как про­из­ве­де­ние ко­ли­че­ства ком­плек­тов пи­та­ния на рас­сто­я­ние от мо­биль­но­го цеха их под­го­тов­ки до пунк­та пи­та­ния спортс­ме­нов на трас­се. Мо­биль­ный цех под­го­тов­ки ком­плек­тов рас­по­ло­жен в одном из пунк­тов пи­та­ния на трас­се таким об­ра­зом, что общая сто­и­мость до­став­ки из цеха во все пунк­ты ми­ни­маль­на.

Опре­де­ли­те ми­ни­маль­ную сум­мар­ную сто­и­мость до­став­ки пи­та­ния для спортс­ме­нов из цеха его под­го­тов­ки в пунк­ты пи­та­ния на трас­се.

Вход­ные дан­ные.

Дано два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит число N (1 ≤ N ≤ 10 000 000)  — ко­ли­че­ство

пунк­тов пи­та­ния на коль­це­вой трас­се. В каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся число  — ко­ли­че­ство ком­плек­тов пи­та­ния на пунк­те (все числа на­ту­раль­ные, ко­ли­че­ство ком­плек­тов пи­та­ния на каж­дом пунк­те не пре­вы­ша­ет 1000). Числа ука­за­ны в по­ряд­ке рас­по­ло­же­ния пунк­тов пи­та­ния спортс­ме­нов на трас­се, на­чи­ная с пер­во­го ки­ло­мет­ра.

Ти­по­вой при­мер ор­га­ни­за­ции дан­ных во вход­ном файле:

6

8

20

5

13

7

19

При таких ис­ход­ных дан­ных, если кон­тей­не­ры уста­нов­ле­ны на каж­дом ки­ло­мет­ре ав­то­до­ро­ги, не­об­хо­ди­мо от­крыть центр пе­ре­ра­бот­ки в пунк­те 6. В этом слу­чае сумма транс­порт­ных за­трат со­ста­вит: 1 · 7 + 0 · 19 + 1 · 8 + 2 · 20 + 3 · 5 + 2 · 13.

Ти­по­вой при­мер имеет ил­лю­стра­тив­ный ха­рак­тер. Для вы­пол­не­ния за­да­ния ис­поль­зуй­те дан­ные из при­ла­га­е­мых фай­лов.

Пре­ду­пре­жде­ние: для об­ра­бот­ки файла B не сле­ду­ет ис­поль­зо­вать пе­ре­бор­ный ал­го­ритм, вы­чис­ля­ю­щий сумму для всех воз­мож­ных ва­ри­ан­тов, по­сколь­ку на­пи­сан­ная по та­ко­му ал­го­рит­му про­грам­ма будет вы­пол­нять­ся слиш­ком долго.

Ответ: