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 = "n = int(input())\r\na = [0] + list(map(int, input().split()))\r\nb = [0] + list(map(int, input().split()))\r\n\r\nps = [0] * (n+1)\r\nfor i in range(1, n+1):\r\n    ps[i] = ps[i-1] + b[i]\r\n\r\nms = [float('-inf')] * (n+1)\r\nfor i in range(1, n+1):\r\n    ms[i] = max(ms[i-1], a[i] - ps[i])\r\n\r\nns = [float('-inf')] * (n+1)\r\nns[n] = a[n] - ps[n]\r\nfor i in range(n-1, 0, -1):\r\n    ns[i] = max(ns[i+1], a[i] - ps[i])\r\n\r\nmaxi = max(a)\r\n\r\nfor j in range(2, n+1):\r\n    maxi = max(maxi, a[j] + ps[j-1] + ms[j-1])\r\n\r\nfor j in range(1, n):\r\n    maxi = max(maxi, a[j] + ps[n] + ps[j-1] + ns[j+1])\r\n\r\nprint(maxi)\r\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: