← 返回题目列表

Codeforces · 987/C

C. 三个显示器

中文机器翻译题面 查看原题

现在是 2018 年年中,住在克拉斯诺卡缅斯克(后贝加尔地区的一个小镇)郊外的玛丽亚·斯捷潘诺夫娜 (Maria Stepanovna) 想租用三台显示器来强调一个重要问题。

沿道路放置了$$$n$$$个显示器,其中第$$$i$$$只能显示字体大小为$$$s_i$$$的文本。 Maria Stepanovna 想租用这样三个显示器,其索引为 $$$i < j < k$$$,如果您沿着道路朝特定方向移动,字体大小就会增加。即,应当满足条件$$$s_i < s_j < s_k$$$。

第 $$$i$$$ 显示器的租金为 $$$c_i$$$。请确定玛丽亚·斯捷潘诺芙娜应支付的最小费用。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 3\,000$$$) — 显示器数量。

第二行包含 $$$n$$$ 整数 $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 10^9$$$) - 显示屏上的字体大小按照沿路排列的顺序排列。

第三行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^8$$$) — 每个显示器的租金成本。

输出

如果没有三个显示器满足条件,则打印 -1。否则,打印一个整数 - 三个显示器的最低总租金成本,其索引为 $$$i < j < k$$$,使得 $$$s_i < s_j < s_k$$$。

示例

输入 #1

5
2 4 5 4 10
40 30 20 10 40

输出 #1

90

输入 #2

3
100 101 100
2 4 5

输出 #2

-1

输入 #3

10
1 2 3 4 5 6 7 8 9 10
10 13 11 14 15 12 13 13 18 13

输出 #3

33

注意

在第一个示例中,例如,您可以选择显示器 $$$1$$$、$$$4$$$ 和 $$$5$$$,因为 $$$s_1 < s_4 < s_5$$$ ($$$2 < 4 < 10$$$),租金成本为 $$$40 + 10 + 40 = 90$$$。

在第二个示例中,您无法选择有效的索引三元组,因此答案为 -1。