Вам задана перестановка $$$p_1, p_2, \dots , p_n$$$ (перестановка — это массив, в котором все числа от $$$1$$$ до $$$n$$$ встречаются ровно один раз). Вес $$$i$$$-го элемента перестановки равен $$$a_i$$$.

Сначала вы делите вашу перестановку на два непустых множества — префикс и суффикс. Более формально, первое множество содержит элементы $$$p_1, p_2, \dots , p_k$$$, второе — $$$p_{k+1}, p_{k+2}, \dots , p_n$$$, где $$$1 \le k < n$$$.

После этого вы можете перемещать элементы между множествами. Точнее, вы можете выбрать элемент первого множества и переместить его во второе множество или наоборот. Вы заплатите $$$a_i$$$ долларов за перемещение элемента $$$p_i$$$.

Ваша задача — сделать так, чтобы любой элемент первого множества был меньше любого элемента второго множества. Обратите внимание, что если одно из множеств пусто, то это условие выполняется.

Например, если $$$p = [3, 1, 2]$$$ и $$$a = [7, 1, 4]$$$, то вам следует действовать следующим образом: разделить $$$p$$$ на две части $$$[3, 1]$$$ и $$$[2]$$$, а затем переместить элемент, равный $$$2$$$, в первое множество (это будет стоить $$$4$$$). А если $$$p = [3, 5, 1, 6, 2, 4]$$$, $$$a = [9, 1, 9, 9, 1, 9]$$$, то нужно делать так: разделить $$$p$$$ на две части $$$[3, 5, 1]$$$ и $$$[6, 2, 4]$$$, а затем переместить элемент, равный $$$2$$$, в первое множество (это стоит $$$1$$$), а элемент, равный $$$5$$$ — во второе (это также стоит $$$1$$$).

Посчитайте минимальное количество долларов, которое вам придется потратить.