UOJ Logo

NOI.AC

1S 128MB
Statistics

挑选蛋糕

时间限制:1秒,内存限制:128MB

读入文件名:cake.in

输出文件名:cake.out

【题目描述】

一家蛋糕店有$n$个蛋糕,蛋糕编号为1到$n$,蛋糕的大小依次为$a_1$到$a_n$,蛋糕的价格依次为$b_1$到$b_n$。

现在你想要挑选三个蛋糕,编号为$i$、$j$、$k$,满足$i\lt j\lt k$,且大小递增,即$a_i\lt a_j\lt a_k$。

问最少要花多少钱,数据保证有解。

【输入格式】

输入有3行,第一行为一个正整数$n$,表示蛋糕的个数。

第二行有$n$个正整数$a_1$到$a_n$,分别表示$n$个蛋糕的大小,用一个空格隔开。

第三行有$n$个正整数$b_1$到$b_n$,分别表示$n$个蛋糕的价格,用一个空格隔开。

【输出格式】

输出一行,包含一个整数,表示买蛋糕的最少花费。

【输入输出样例1】

cake.in

5
2 4 5 4 10
40 30 20 10 40

cake.out

90

【输入输出样例2】

cake.in

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

cake.out

33

【数据规模与约定】

对于前30%的数据,$1\le b_i\le 100$;

对于前60%的数据,$1\le n\le 100$;

对于100%的数据,$1\le n\le 5000$,$1\le a_i,b_i\le 10^9$;