Special Sums

Indian National Olympiad in Informatics 2015
In this problem you are given two lists of N integers, a_{1, }a_{2, ..., }a_{N} and b_{1,} b_{2, ...} b_{N}. For any pair (i, j) with i, j ϵ {1, 2, ..., N} we define the segment from i to j, written as [i, j], to be i, i + 1, ..., j if i ≤ j and i, i + 1, ..., N, 1, 2, ...,j if i > j. Thus if N = 5 then the [2, 4] = {2, 3, 4} and [4, 2] = {4, 5, 1, 2}.
With each segment [i, j] we associate a special sum SSum[i, j] as follows:
 SSum[i, i] = a_{i}.
 If i ≠ j then,
The positions i and j contribute a_{i }and a_{j}, respectively, to the sum while every other position k in [i, j] contributes b_{k}.
Suppose N = 5 and that the two given sequences are as follows:
i 
1 
2 
3 
4 
5 
a_{i} 
2 
3 
2 
3 
1 
^{b}i 
3 
4 
4 
6 
3 
Then, SSum[1, 1] = 2, SSum[2, 4] = 3 + 4 + 3 = 10 and SSum[4, 2] = 3 + 3 + 3 + 3 = 12. Your aim is to compute the maximum value of SSum[i, j] over all segments [i, j]. In this example you can verify that this value is 18 (SSum[2, 1] = 18).
Input format
 The first line contains a single positive integer N.
 This is followed by a line containing N integers giving the values of the a_{i}s and this is followed by a line containing N integers giving the values of the b_{i}s.
Output format
A single integer in a single line giving the maximum possible special segment sum.
Note: The final value may not fit in a 32 bit integer. Use variables of an appropriate type to store and manipulate this value (long long in C/C++, long in Java).
Test Data
You may assume that 10^{9} ≤ a_{i,} b_{i} ≤ 10^{9}.
Subtask 1 (10 Marks) 1 ≤ N ≤ 3000.
Subtask 2 (20 Marks) 1 ≤ N ≤ 10^{6} and a_{i} = b_{i} for all 1 ≤ i ≤ N.
Subtask 3 (30 Marks) 3 ≤ N ≤10^{6}. Further a_{1} = b_{1} = a_{N} = b_{N} = 10_{9} and for each
1 < k < N we have 999 ≤ a_{k,} b_{k} ≤ 999.
Subtask 4 (40 Marks) 1 ≤ N ≤ 10^{6}.
Example
Here is the sample input and output corresponding to the example above:
Sample input
5
2 3 2 3 1
3 4 4 6 3
Sample output
18
Note: Your program should not print anything other than what is specified in the output format. Please remove all diagnostic print statements before making your final submission. A program with extraneous output will be treated as incorrect!
Author:  admin3 
Date Added:  2012016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, C99 strict, CPP 4.3.2, CPP 4.9.2, CPP14, JAVA, PYTH, PYTH 3.4 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions