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 = '# import all important libraries and inbuilt functions\n\nfrom fractions import Fraction\nimport numpy as np\nimport sys,bisect,copyreg,copy,statistics,os\nfrom math import *\nfrom collections import Counter,defaultdict,deque,OrderedDict   \nfrom itertools import combinations,permutations,accumulate,groupby \nfrom numpy.linalg import matrix_power as mp\nfrom bisect import bisect_left,bisect_right,bisect,insort,insort_left,insort_right\nfrom statistics import mode\nfrom functools import reduce,cmp_to_key \nfrom io import BytesIO, IOBase\nfrom scipy.spatial import ConvexHull\nfrom heapq import *\nfrom decimal import *\nfrom queue import Queue,PriorityQueue\nfrom re import sub,subn\n\n# end of library import\n\n# map system version faults\nif sys.version_info[0] < 3:\n    from builtins import xrange as range\n    from future_builtins import ascii, filter, hex, map, oct, zip\n\n# template of many functions used in competitive programming can add more later \n# based on need we will use this commonly.\n\n# bfs in a graph\ndef bfs(adj,v): # a schema of bfs\n    visited=[False]*(v+1);q=deque()\n    while q:pass\n\n# definition of vertex of a graph\ndef graph(vertex): return [[] for i in range(vertex+1)]\n\ndef powermodulo(x, y, p) : \n    res = 1;x = x % p        \n    if (x == 0) : return 0  \n    while (y > 0) : \n        if ((y & 1) == 1) :   res = (res * x) % p \n        y = y >> 1 \n        x = (x * x) % p           \n    return res\n\ndef lcm(a,b): return (a*b)//gcd(a,b)\n\n# most common list in a array of lists\ndef most_frequent(List):return Counter(List).most_common(1)[0][0]\n\n# element with highest frequency\ndef most_common(List):return(mode(List))\n\n#In number theory, the Chinese remainder theorem states that \n#if one knows the remainders of the Euclidean division of an integer n by \n#several integers, then one can determine uniquely the remainder of the \n#division of n by the product of these integers, under the condition \n#that the divisors are pairwise coprime.\ndef chinese_remainder(a, p):\n    prod = reduce(op.mul, p, 1);x = [prod // pi for pi in p]\n    return sum(a[i] * powermodulo(x[i], p[i] - 2, p[i]) * x[i] for i in range(len(a))) % prod\n\n# make a matrix\ndef createMatrix(rowCount, colCount, dataList):   \n    mat = []\n    for i in range (rowCount):\n        rowList = []\n        for j in range (colCount):\n            if dataList[j] not in mat:rowList.append(dataList[j])\n        mat.append(rowList) \n    return mat\n\n# input for a binary tree\ndef readTree(): \n    v=int(inp());adj=[set() for i in range(v+1)]\n    for i in range(v-1):u1,u2=In(); adj[u1].add(u2);adj[u2].add(u1)\n    return adj,v\n    \n# sieve of prime numbers    \ndef sieve():\n    li=[True]*1000001;li[0],li[1]=False,False;prime=[]\n    for i in range(2,len(li),1):\n        if li[i]==True:\n            for j in range(i*i,len(li),i):li[j]=False    \n    for i in range(1000001):\n        if li[i]==True:prime.append(i)\n    return prime\n\n#count setbits of a number.\ndef setBit(n):\n    count=0\n    while n!=0:n=n&(n-1);count+=1\n    return count\n\n# sum of digits of a number\ndef digitsSum(n):\n    if n == 0:return 0\n    r = 0\n    while n > 0:r += n % 10;n //= 10\n    return r\n\n# ncr efficiently\ndef ncr(n, r):\n    r = min(r, n - r);numer = reduce(op.mul, list(range(n, n - r, -1)), 1);denom = reduce(op.mul, list(range(1, r + 1)), 1)\n    return numer // denom  # or / in Python 2\n\n#factors of a number\ndef factors(n):return list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))\n\n#prime fators of a number\ndef prime_factors(n):\n    i = 2;factors = []\n    while i * i <= n:\n        if n % i:i += 1\n        else:n //= i;factors.append(i)\n    if n > 1:factors.append(n)\n    return len(set(factors))\n\ndef prefixSum(arr):\n    for i in range(1, len(arr)):arr[i] = arr[i] + arr[i-1]\n    return arr    \n\ndef binomial_coefficient(n, k):\n    if 0 <= k <= n:\n        ntok = 1;ktok = 1\n        for t in range(1, min(k, n - k) + 1):ntok *= n;ktok *= t;n -= 1\n        return ntok // ktok\n    else:return 0\n \ndef powerOfK(k, max):\n    if k == 1:return [1]\n    if k == -1:return [-1, 1] \n    result = [];n = 1\n    while n <= max:result.append(n);n *= k\n    return result\n\n# maximum subarray sum use kadane\'s algorithm\ndef kadane(a,size):\n    max_so_far = 0;max_ending_here = 0 \n    for i in range(0, size):\n        max_ending_here = max_ending_here + a[i]\n        if (max_so_far < max_ending_here):max_so_far = max_ending_here \n        if max_ending_here < 0:max_ending_here = 0\n    return max_so_far                                    \n                  \ndef divisors(n):\n    result = []\n    for i in range(1,ceil(sqrt(n))+1):\n        if n%i == 0:\n            if n/i == i:result.append(i)\n            else:result.append(i);result.append(n/i)\n    return result\n\ndef sumtilln(n): return ((n*(n+1))//2)\n\ndef isPrime(n) : \n\tif (n <= 1) :return False\n\tif (n <= 3) :return True\n\tif (n % 2 == 0 or n % 3 == 0) :return False\n\tfor i in range(5,ceil(sqrt(n))+1,6):\n\t\tif (n % i == 0 or n % (i + 2) == 0) :return False\n\treturn True\n\ndef isPowerOf2(n):\n    while n % 2 == 0:n //= 2\n    return (True if n == 1 else False)\n\ndef power2(n):\n    k = 0\n    while n % 2 == 0:k += 1;n //= 2\n    return k\n\ndef sqsum(n):return ((n*(n+1))*(2*n+1)//6)\n    \ndef cusum(n):return ((sumn(n))**2)\n\ndef pa(a):\n    for i in range(len(a)):print(a[i], end = " ")\n    print()\n\ndef pm(a,rown,coln):\n    for i in range(rown):\n        for j in range(coln):print(a[i][j],end = " ")\n        print()\n\ndef pmasstring(a,rown,coln):\n    for i in range(rown):\n        for j in range(coln):print(a[i][j],end = "")\n        print()\n        \ndef isPerfectSquare(n):return pow(floor(sqrt(n)),2) == n\n\ndef nC2(n,m):return (((n*(n-1))//2) % m)\n\ndef modInverse(n,p):return powermodulo(n,p-2,p)\n\ndef ncrmodp(n, r, p):  \n\tnum = den = 1\n\tfor i in range(r):num = (num * (n - i)) % p ;den = (den * (i + 1)) % p \n\treturn (num * powermodulo(den,p - 2, p)) % p \n\ndef reverse(string):return "".join(reversed(string))        \n\ndef listtostr(s):return \' \'.join([str(elem) for elem in s]) \n\ndef binarySearch(arr, l, r, x): \n\twhile l <= r: \n\t\tmid = l + (r - l) // 2; \n\t\tif arr[mid] == x:return mid \n\t\telif arr[mid] < x:l = mid + 1\n\t\telse:r = mid - 1\n\treturn -1\n\ndef isarrayodd(a):\n    r = True\n    for i in range(len(a)):\n        if a[i] % 2 == 0:\n            r = False\n            break\n    return r\n\ndef isPalindrome(s):return s == s[::-1] \n\ndef gt(x,h,c,t):return ((x*h+(x-1)*c)/(2*x-1))\n\ndef CountFrequency(my_list): \n    freq = {} \n    for item in my_list:freq[item] = (freq[item] + 1 if (item in freq) else 1)\n    return freq\n\ndef CountFrequencyasPair(my_list1,my_list2,freq): \n    for item in my_list1:freq[item][0] = (freq[item][0] + 1 if (item in freq) else 1)\n    for item in my_list2:freq[item][1] = (freq[item][1] + 1 if (item in freq) else 1)     \n    return freq \n \ndef binarySearchCount(arr, n, key):   \n    left = 0;right = n - 1;count = 0  \n    while (left <= right):  \n        mid = int((right + left) / 2) \n        if (arr[mid] <= key):count,left = mid + 1,mid + 1\n        else:right = mid - 1      \n    return count\n\ndef primes(n):\n  sieve,l = [True] * (n+1),[]\n  for p in range(2, n+1):\n    if (sieve[p]):\n      l.append(p)\n      for i in range(p, n+1, p):sieve[i] = False\n  return l\n\ndef Next_Greater_Element_for_all_in_array(arr): \n\ts,n,reta,retb = list(),len(arr),[],[];arr1 = [list([0,i]) for i in range(n)]\n\tfor i in range(n - 1, -1, -1): \n\t\twhile (len(s) > 0 and s[-1][0] <= arr[i]):s.pop() \n\t\tif (len(s) == 0):arr1[i][0] = -1\t\t\t\t\t\n\t\telse:arr1[i][0] = s[-1]\t \n\t\ts.append(list([arr[i],i]))\t\t\n\tfor i in range(n):reta.append(list([arr[i],i]));retb.append(arr1[i][0])\n\treturn reta,retb\n\ndef polygonArea(X,Y,n):   \n    area = 0.0;j = n - 1\n    for i in range(n):area += (X[j] + X[i]) * (Y[j] - Y[i]);j = i   \n    return abs(area / 2.0)\n\ndef merge(a, b):\n\tans = defaultdict(int)\n\tfor i in a:ans[i] += a[i]\n\tfor i in b:ans[i] += b[i]\n\treturn ans\n \n#defining a LRU Cache\n# where we can set values and get values based on our requirement\nclass LRUCache: \n\t# initialising capacity \n\tdef __init__(self, capacity: int): \n\t\tself.cache = OrderedDict() \n\t\tself.capacity = capacity \n\n\t# we return the value of the key \n\t# that is queried in O(1) and return -1 if we \n\t# don\'t find the key in out dict / cache. \n\t# And also move the key to the end \n\t# to show that it was recently used. \n\tdef get(self, key: int) -> int: \n\t\tif key not in self.cache:return -1\n\t\telse:self.cache.move_to_end(key);return self.cache[key] \n\n\t# first, we add / update the key by conventional methods. \n\t# And also move the key to the end to show that it was recently used. \n\t# But here we will also check whether the length of our \n\t# ordered dictionary has exceeded our capacity, \n\t# If so we remove the first key (least recently used) \n\tdef put(self, key: int, value: int) -> None: \n\t\tself.cache[key] = value;self.cache.move_to_end(key) \n\t\tif len(self.cache) > self.capacity:self.cache.popitem(last = False)\n\nclass segtree:\n    def __init__(self,n):\n        self.m = 1\n        while self.m < n:self.m *= 2\n        self.data = [0] * (2 * self.m)\n    def __setitem__(self,i,x):\n        x = +(x != 1);i += self.m;self.data[i] = x;i >>= 1\n        while i:self.data[i] = self.data[2 * i] + self.data[2 * i + 1];i >>= 1\n    def __call__(self,l,r):\n        l += self.m;r += self.m;s = 0\n        while l < r:\n            if l & 1:s += self.data[l];l += 1\n            if r & 1:r -= 1;s += self.data[r]\n            l >>= 1;r >>= 1\n        return s        \n\nclass FenwickTree:\n  def __init__(self, n):self.n = n;self.bit = [0]*(n+1)  \n  def update(self, x, d):\n    while x <= self.n:self.bit[x] += d;x += (x & (-x))  \n  def query(self, x):\n    res = 0\n    while x > 0:res += self.bit[x];x -= (x & (-x))\n    return res\n  def range_query(self, l, r):return self.query(r) - self.query(l-1)        \n# can add more template functions here\n    \n# end of template functions\n\n# To enable the file I/O i the below 2 lines are uncommented.\n# read from in.txt if uncommented\nif os.path.exists(\'in.txt\'): sys.stdin=open(\'in.txt\',\'r\')\n# will print on Console if file I/O is not activated\n#if os.path.exists(\'out.txt\'): sys.stdout=open(\'out.txt\', \'w\')\n\n# inputs template\n#for fast input we areusing sys.stdin\ndef inp(): return sys.stdin.readline().strip()\n\n#for fast output, always take string\ndef out(var): sys.stdout.write(str(var))  \n\n# cusom base input needed for the program\ndef I():return (inp())\ndef II():return (int(inp()))\ndef FI():return (float(inp()))\ndef SI():return (list(str(inp())))\ndef MI():return (map(int,inp().split()))\ndef LI():return (list(MI()))\ndef SLI():return (sorted(LI()))\ndef MF():return (map(float,inp().split()))\ndef LF():return (list(MF()))\ndef SLF():return (sorted(LF()))\n\n# end of inputs template\n\n# common modulo values used in competitive programming\nMOD = 998244353\nmod = 10**9+7\n\n# any particular user-defined functions for the code.\n# can be written here.  \n \n# end of any user-defined functions\n\n# main functions for execution of the program.\ndef __starting_point():  \n    # execute your program from here.\n    # start your main code from here\n        \n    # Write your code here\n    n = II()\n    a,b = LI(),LI()\n    pb,pr = [],0\n    for i in b:\n        pr += i\n        pb.append(pr)\n    mi,mj = [0]*n,[0]*n\n    mj[0] = a[0]-pb[0]\n    for i in range(1,n):\n        mj[i] = max(mj[i-1],a[i]-pb[i])\n    mi[0] = a[0]\n    for i in range(1,n):\n        mi[i] = max(mi[i-1],a[i]+pb[i-1])\n    ans = a[0]\n    for i in range(1,n):\n        ans = max(ans,a[i],a[i]+ pb[i-1]+ mj[i-1] , a[i] + pb[n-1]-pb[i] + mi[i-1])\n    print(ans)\n    \n    # end of main code\n    # end of program\n\n# This program is written by :\n#   Shubham Gupta\n#   B.Tech (2019-2023)\n#   Computer Science and Engineering,\n#   Department of EECS\n#   Contact No:8431624358\n#   Indian Institute of Technology(IIT),Bhilai\n#   Sejbahar,\n#   Datrenga,\n#   Raipur,\n#   Chhattisgarh\n#   492015\n\n#   THANK YOU FOR \n#YOUR KIND PATIENCE FOR READING THE PROGRAM.    \n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: