Низом чудних догађаја, чланови Комисије су постали власници складишта, у којем се кутије држе поређане у низ. Сваки пут када се достава појави да би испоручила нову кутију, потребно је одлучити да ли ће им се отворити предња или задња врата, односно да ли ће кутија бити додата на почетак или крај низа.

Када је потребно извадити кутију из складишта, члан Комисије који последњи смисли разлог зашто баш он нема времена мора да уђе на предња врата, пронађе тражену кутију, изнесе је и среди складиште. Ако је кутија на позицији \(i\), рачунато од почетка низа (прва кутија је на позицији \(0\)), ова операција траје \(i\) наносекунди. Сређивање укључује “поправљање” низа, тако да неће остати празно место (све кутије након \(i\)-те ће се померити за једно место).

Пошто Комисија тренутно баш и нема времена, замолили су вас да преузмете доношење одлука током доставе. Добили сте распоред за данас, у ком је дато време доставе и одношења сваке кутије. Ваш задатак је да одредите колико је најмање времена потребно провести у вађењу кутија (у наносекундама).

Описи функција

Потребно је да имплементирате следећу функцију:

• \(Resi(N, A[\ldots], B[\ldots])\)

\(N\) је број кутија које ће током дана бити достављене у складиште (и касније извађене), \(A\) и \(B\) су низови дужине \(N\) у којима је дат распоред – \(A_i\) је време доставе \(i\)-те кутије (у минутима), а \(B_i\) време када ће Комисија извадити исту кутију из складишта.

Функција треба да врати цео број \(T\) – време које ће Комисија провести у складишту (у наносекундама), ако су доставе усмерене тако да је ово време минимизовано. Сви низови су индексирани од 0.

Пример

Нека је \(N = 4\), \(A = [0, 1, 2, 5]\) и \(B = [3, 7, 4, 6]\). Ови параметри одговарају следећем редоследу догађаја:

• кутије 1, 2 и 3 се редом доносе у складиште,
• кутије 1 и 3 (редом) се ваде из складишта,
• кутија 4 се доноси, и
• кутије 4 и 2 се ваде.

Оптималан распоред достава је: кутије 1, 2 и 4 доставити на задња врата, а 3 на предња. У овом случају, све кутије осим 1 ће бити прве у складишту када се ваде, а кутија 1 ће бити друга, тако да је укупно време \(1\) наносекунда.

Ограничења

• \(1 \leq N \leq 10^5\)
• \(0 \leq A_i, B_i < 2N\)
• све вредности \(A_i\) и \(B_i\) су међусобно различите

Подзадаци

• Подзадатак 1 [20 поена]: \(N \leq 20\)
• Подзадатак 2 [40 поена]: \(N \leq 3000\)
• Подзадатак 3 [21 поена]: \(\forall i,j . A_i < B_j\)
• Подзадатак 4 [19 поена]: Нема додатних ограничења

Детаљи имплементације

Потребно је да пошаљете тачно један фајл skladiste.cpp који имплементира поменfуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

long long Resi(int N, int *A, int *B)

Вашим програмима је дозвољено да мењају садржај низова/матрица, али не смеју да приступају ван граница датих низова.

Уз задатак, обезбеђен вам је “template” фајл code.cpp које можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке:

• y првом реду број \(N\), и
• у наредних \(N\) редова по два броја: вредности \(A_i\) и \(B_i\).

Затим овај програм зове вашу функцију и штампа повратну вредност \(T\). Кодове ових програма можете мењати по потреби.