{"raw_statement":[{"iden":"statement","content":"It is the middle of 2018 and Maria Stepanovna, who lives outside Krasnokamensk (a town in Zabaikalsky region), wants to rent three displays to highlight an important problem.\n\nThere are $n$ displays placed along a road, and the $i$\\-th of them can display a text with font size $s_i$ only. Maria Stepanovna wants to rent such three displays with indices $i &lt; j &lt; k$ that the font size increases if you move along the road in a particular direction. Namely, the condition $s_i &lt; s_j &lt; s_k$ should be held.\n\nThe rent cost is for the $i$\\-th display is $c_i$. Please determine the smallest cost Maria Stepanovna should pay."},{"iden":"input","content":"The first line contains a single integer $n$ ($3 \\le n \\le 3\\,000$) — the number of displays.\n\nThe second line contains $n$ integers $s_1, s_2, \\ldots, s_n$ ($1 \\le s_i \\le 10^9$) — the font sizes on the displays in the order they stand along the road.\n\nThe third line contains $n$ integers $c_1, c_2, \\ldots, c_n$ ($1 \\le c_i \\le 10^8$) — the rent costs for each display."},{"iden":"output","content":"If there are no three displays that satisfy the criteria, print _\\-1_. Otherwise print a single integer — the minimum total rent cost of three displays with indices $i &lt; j &lt; k$ such that $s_i &lt; s_j &lt; s_k$."},{"iden":"examples","content":"Input\n\n5\n2 4 5 4 10\n40 30 20 10 40\n\nOutput\n\n90\n\nInput\n\n3\n100 101 100\n2 4 5\n\nOutput\n\n\\-1\n\nInput\n\n10\n1 2 3 4 5 6 7 8 9 10\n10 13 11 14 15 12 13 13 18 13\n\nOutput\n\n33"},{"iden":"note","content":"In the first example you can, for example, choose displays $1$, $4$ and $5$, because $s_1 &lt; s_4 &lt; s_5$ ($2 &lt; 4 &lt; 10$), and the rent cost is $40 + 10 + 40 = 90$.\n\nIn the second example you can't select a valid triple of indices, so the answer is _\\-1_."}],"translated_statement":[{"iden":"statement","content":"现在是2018年中期，住在克拉斯诺卡门斯克（扎巴伊卡利斯基地区的一个城镇）外的玛丽亚·斯捷潘诺夫娜想租用三块显示屏来突出一个重要问题。\n\n沿路摆放着 $n$ 块显示屏，第 $i$ 块显示屏只能显示字体大小为 $s_i$ 的文本。玛丽亚·斯捷潘诺夫娜希望租用三块显示屏，其下标满足 $i < j < k$，且沿道路某一方向移动时，字体大小递增。即需满足条件 $s_i < s_j < s_k$。\n\n第 $i$ 块显示屏的租金为 $c_i$。请确定玛丽亚·斯捷潘诺夫娜应支付的最小租金。\n\n第一行包含一个整数 $n$（$3 lt.eq n lt.eq 3 thin 000$）——显示屏的数量。\n\n第二行包含 $n$ 个整数 $s_1, s_2, dots.h, s_n$（$1 lt.eq s_i lt.eq 10^9$）——沿道路顺序排列的显示屏的字体大小。\n\n第三行包含 $n$ 个整数 $c_1, c_2, dots.h, c_n$（$1 lt.eq c_i lt.eq 10^8$）——每个显示屏的租金。\n\n如果没有三块显示屏满足条件，请输出 _-1_。否则输出一个整数——满足 $i < j < k$ 且 $s_i < s_j < s_k$ 的三块显示屏的最小总租金。\n\n在第一个例子中，你可以选择显示屏 $1$、$4$ 和 $5$，因为 $s_1 < s_4 < s_5$（$2 < 4 < 10$），租金为 $40 + 10 + 40 = 90$。\n\n在第二个例子中，无法选出满足条件的三元组下标，因此答案为 _-1_。\n\n"},{"iden":"input","content":"第一行包含一个整数 $n$（$3 lt.eq n lt.eq 3 thin 000$）——显示屏的数量。第二行包含 $n$ 个整数 $s_1, s_2, dots.h, s_n$（$1 lt.eq s_i lt.eq 10^9$）——沿道路顺序排列的显示屏的字体大小。第三行包含 $n$ 个整数 $c_1, c_2, dots.h, c_n$（$1 lt.eq c_i lt.eq 10^8$）——每个显示屏的租金。"},{"iden":"output","content":"如果没有三块显示屏满足条件，请输出 _-1_。否则输出一个整数——满足 $i < j < k$ 且 $s_i < s_j < s_k$ 的三块显示屏的最小总租金。"},{"iden":"examples","content":"输入52 4 5 4 1040 30 20 10 40输出90输入3100 101 1002 4 5输出-1输入101 2 3 4 5 6 7 8 9 1010 13 11 14 15 12 13 13 18 13输出33"},{"iden":"note","content":"在第一个例子中，你可以选择显示屏 $1$、$4$ 和 $5$，因为 $s_1 < s_4 < s_5$（$2 < 4 < 10$），租金为 $40 + 10 + 40 = 90$。在第二个例子中，无法选出满足条件的三元组下标，因此答案为 _-1_。"}],"sample_group":[],"show_order":[],"formal_statement":"Given:  \n- $ n \\in \\mathbb{N} $, $ 3 \\leq n \\leq 3000 $  \n- Two sequences $ s = (s_1, s_2, \\dots, s_n) $, $ c = (c_1, c_2, \\dots, c_n) $, where $ s_i \\in [1, 10^9] $, $ c_i \\in [1, 10^8] $  \n\nFind:  \n- Minimum value of $ c_i + c_j + c_k $ over all triples $ (i, j, k) $ such that $ 1 \\leq i < j < k \\leq n $ and $ s_i < s_j < s_k $  \n\nIf no such triple exists, return $ -1 $.","simple_statement":null,"has_page_source":false}