2406: 按摩座椅
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：10
Solved：1
Description
狐狸尼克的经商头脑很灵活，他看到电影院有很多人等候时没有足够的座椅，于是他抓住了这个商机，在电影院门口投放了很多按摩座椅，供人们使用。
狐狸尼克一共投放 2n+2 个按摩座椅并排成一行，每个按摩座椅有且只有一个座位。从左数第 i (1<=i<=2n) 个座椅的舒适度为 ai。现有 n 对结伴而来的情侣客人，以及 2 位单身来访的 VIP 客人，狐狸尼克需要为这 2n+2 位客人每人分配一个座位。但是，不能将同一个座位分配给两位或更多的客人。
现在，对于属于同一对情侣的两个人，必须分配相邻的座位。在此条件下，狐狸尼克希望分配给两位单身来访的 VIP 客人的两个座位的舒适度之和尽可能大。
给定每个按摩座椅的舒适度信息，请编写一个程序，求出尼克分配给两位单身来访的 VIP 客人的两个座位的舒适度之和的最大值。
数据范围：1<=n<=200000, 1<=ai<=1e9
狐狸尼克一共投放 2n+2 个按摩座椅并排成一行，每个按摩座椅有且只有一个座位。从左数第 i (1<=i<=2n) 个座椅的舒适度为 ai。现有 n 对结伴而来的情侣客人，以及 2 位单身来访的 VIP 客人，狐狸尼克需要为这 2n+2 位客人每人分配一个座位。但是，不能将同一个座位分配给两位或更多的客人。
现在，对于属于同一对情侣的两个人，必须分配相邻的座位。在此条件下，狐狸尼克希望分配给两位单身来访的 VIP 客人的两个座位的舒适度之和尽可能大。
给定每个按摩座椅的舒适度信息，请编写一个程序，求出尼克分配给两位单身来访的 VIP 客人的两个座位的舒适度之和的最大值。
数据范围：1<=n<=200000, 1<=ai<=1e9
Input
第一行包含一个整数 n。
第二行包含 2n+2 个整数，第 i (1<=i<=2n) 个整数为 ai，表示第 i 个按摩座椅的舒适度。
第二行包含 2n+2 个整数，第 i (1<=i<=2n) 个整数为 ai，表示第 i 个按摩座椅的舒适度。
Output
输出共一行一个整数，即分配给两位单身来访的 VIP 客人的两个座位的舒适度之和的最大值。
Sample Input Copy
2
20 60 40 30 10 50Sample Output Copy
90HINT
【样例1解释】
狐狸尼克通过如下分配，可以使得两位单身来访的 VIP 客人的座位舒适度之和达到 90 。
为第 1 对情侣分配从左数第 1 ,2 号座位。为第 2 对情侣分配从左数第 4,5 号座位。为两位单身来访的 VIP 客人分配从左数第 3, 6号座位。这也是最优解，输出 90。
【输入样例2】
1
1000000000 1000000000 1 1
【输出样例2】
2000000000
【输入样例3】
4
4 10 8 6 7 6 7 8 12 3
【输出样例3】
16