Indian National Olympiad in Informatics 2015
In this problem you are given two lists of N integers, a1, a2, ..., aN and b1, b2, ... bN. 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] = ai.
- If i ≠ j then, 

The positions i and j contribute ai and aj, respectively, to the sum while every other position k in [i, j] contributes bk.
Suppose N = 5 and that the two given sequences are as follows:
i
1
2
3
4
5
ai
2
3
2
3
1
bi
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 ais and this is followed by a line containing N integers giving the values of the bis.

-----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 -109 ≤ ai, bi ≤ 109.
Subtask 1 (10 Marks) 1 ≤ N ≤ 3000.
Subtask 2 (20 Marks) 1 ≤ N ≤ 106 and ai = bi for all 1 ≤ i ≤ N.
Subtask 3 (30 Marks) 3 ≤ N ≤106. Further a1 = b1 = aN = bN = -109 and for each
1 < k < N we have -999 ≤ ak, bk ≤ 999.
Subtask 4 (40 Marks) 1 ≤ N ≤ 106.

-----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!

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\nn = int(input())\na = list(map(int,input().strip().split()))\nb = list(map(int,input().strip().split()))\n\np = [b[0]]\nc = []\nd = []\nfor i in range(1,n):\n    p.append(p[i-1]+b[i])\nfor i in range(n):\n    c.append(a[i]-p[i])\n    d.append(a[i]+p[i-1])\n\ne = c.index(max(c))\nl = c.index(max(c[1:]))\nm = d.index(max(d[:n-1]))\nf = d.index(max(d))\nk = d.index(max(d[1:]))\ng = -10000000000\nh = -10000000000\nif(len(d[1:e])!=0):\n    g = c[l]+ max(d[1:l]) + p[n-1]\nif(len(c[k+1:])!=0):\n    h = d[k] + max(c[k+1:]) + p[n-1]\n\ns1 = max(g,h,max(c[1:])+a[0]+p[n-1])\nh = -10000000000\ng = d[k]+max(c[:k])\nif(len(d[e+1:])!=0):\n    h = c[e]+max(d[e+1:])\ns2 = max(g,h)\nprint(max(max(a),s1,s2))\n\n\n    \n    \n#maxa = a[n-1]\n#for i in range(n-1):\n #   maxa = max(a[i],maxa)\n  #  for j in range(i+1,n):\n   #     ssumi = a[i] + a[j]\n    #    if(j - i == 1):\n     #       if(i>=1):\n      #          ssumi += max(0,p[n-1]+p[i-1]-p[j])\n       #     else:\n        #        ssumi += max(0,p[n-1]-p[j])\n        #else:\n         #   if(i>=1):\n          #      ssumi += max(p[j-1]-p[i],p[n-1]- p[j]+ p[i-1])\n           # else:\n            #    ssumi += max(p[j-1]-p[i],p[n-1]- p[j])\n        #print(i,j,ssumi)\n        #if(ssum < ssumi):\n         #   ssum = ssumi\n#print(max(ssum,maxa),maxa)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: