{"problem":{"name":"C. Three displays","description":{"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. There are $n$ displays p","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF987C"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe 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.\n\n## Output\n\nIf 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$.\n\n[samples]\n\n## Note\n\nIn 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_.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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## Input\n\n第一行包含一个整数 $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$）——每个显示屏的租金。\n\n## Output\n\n如果没有三块显示屏满足条件，请输出 _-1_。否则输出一个整数——满足 $i < j < k$ 且 $s_i < s_j < s_k$ 的三块显示屏的最小总租金。\n\n[samples]\n\n## Note\n\n在第一个例子中，你可以选择显示屏 $1$、$4$ 和 $5$，因为 $s_1 < s_4 < s_5$（$2 < 4 < 10$），租金为 $40 + 10 + 40 = 90$。在第二个例子中，无法选出满足条件的三元组下标，因此答案为 _-1_。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF987C","tags":["brute force","dp","implementation"],"sample_group":[["5\n2 4 5 4 10\n40 30 20 10 40","90"],["3\n100 101 100\n2 4 5","\\-1"],["10\n1 2 3 4 5 6 7 8 9 10\n10 13 11 14 15 12 13 13 18 13","33"]],"created_at":"2026-03-03 11:00:39"}}