现在是 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。