You are given two sorted arrays of distinct integers nums1 and nums2.
A valid path is defined as follows:

Choose array nums1 or nums2 to traverse (from index-0).
Traverse the current array from left to right.
If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

Score is defined as the sum of uniques values in a valid path.
Return the maximum score you can obtain of all possible valid paths.
Since the answer may be too large, return it modulo 10^9 + 7.
 
Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].

Example 2:
Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].

Example 3:
Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].

Example 4:
Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61

 
Constraints:

1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 and nums2 are strictly increasing.

Difficulty: interview

Starter code:

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        

Solutions:
class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        d2 = {nums2[i]:i for i in range(len(nums2))}
        _nums1 = []
        _nums2 = []
        prev_i, prev_j = 0, 0
        for i in range(len(nums1)):
            if nums1[i] in d2:
                _nums1.append(sum(nums1[prev_i:i]))
                _nums2.append(sum(nums2[prev_j:d2[nums1[i]]]))
                _nums1.append(nums1[i])
                _nums2.append(nums1[i])
                prev_i = i+1
                prev_j = d2[nums1[i]]+1
        _nums1.append(sum(nums1[prev_i:]))
        _nums2.append(sum(nums2[prev_j:]))
        print(_nums1)
        print(_nums2)
        n = len(_nums1)
        ans = 0
        for i in range(n):
            ans += max(_nums1[i], _nums2[i])
        return ans % (10**9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        i, j = 0, 0
        n1, n2 = len(nums1), len(nums2)
        
        total1 = 0
        total2 = 0
        while i < n1 or j < n2:
            v1 = nums1[i] if i < n1 else math.inf
            v2 = nums2[j] if j < n2 else math.inf
            
            if v1 < v2:
                total1 += v1
                i += 1
            elif v2 < v1:
                total2 += v2
                j += 1
            elif v1 == v2:
                total = max(total1 + v1, total2 + v2)
                total1 = total
                total2 = total
                i += 1
                j += 1
            
        return max(total1, total2) % (10**9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        i1, i2, n1, n2, f1, f2 = 0, 0, len(nums1), len(nums2), 0, 0
        while i1 < n1 or i2 < n2:
            if i1 == n1:
                f2 += sum(nums2[i2:])
                i2 = n2
                continue
            if i2 == n2: 
                f1 += sum(nums1[i1:])
                i1 = n1
                continue
            if nums1[i1] < nums2[i2]:
                f1 += nums1[i1]
                i1 += 1
                continue
            if nums1[i1] > nums2[i2]:
                f2 += nums2[i2]
                i2 += 1
                continue
            f1 = f2 = max(f2 + nums2[i2], f1 + nums1[i1])     
            i1 += 1
            i2 += 1
        return max(f1, f2) % 1000000007

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        i, j = 0, 0
        a, b = 0, 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                a += nums1[i]
                i += 1
            elif nums1[i] > nums2[j]:
                b += nums2[j]
                j += 1
            else:
                a = b = max(a, b) + nums1[i]
                i += 1
                j += 1
        
        if i != len(nums1):
            a = max(b, a + sum(nums1[i:]))
            
        elif j != len(nums2):
            a = max(a, b + sum(nums2[j:]))
            
        return a % (10 ** 9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        m = len(nums2)
        
        t1 = [0 for _ in range(n+1)]
        t2 = [0 for _ in range(m+1)]
        i,j = 1,1
        
        while i<n+1 and j <m+1:
            if nums1[i-1]==nums2[j-1]:
                t1[i] = max(t1[i-1],t2[j-1]) + nums1[i-1]
                t2[j] = max(t1[i-1],t2[j-1]) + nums2[j-1]
                
                i+=1
                j+=1
            
            elif nums1[i-1] < nums2[j-1]:
                t1[i] = t1[i-1] + nums1[i-1]
                i+=1
            
            else:
                t2[j] = t2[j-1] + nums2[j-1]
                j+=1
        
        while i<n+1:
            t1[i] = t1[i-1] + nums1[i-1]
            i+=1
        
        while j<m+1:
            t2[j] = t2[j-1] + nums2[j-1]
            j+=1
        
        
        return max(t1[-1],t2[-1]) % (10**9 + 7)         

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        indeg = defaultdict(int)
        g = defaultdict(list)
        
        for i in range(len(nums1)-1):
            g[nums1[i]].append(nums1[i+1])
            indeg[nums1[i+1]] += 1
        for i in range(len(nums2)-1):
            g[nums2[i]].append(nums2[i+1])
            indeg[nums2[i+1]] += 1
        
        q = deque()
        ans = 0
        dists = defaultdict(int)
        for num in g:
            if indeg[num] == 0:
                q.append((num, num))
                dists[num] = num
        
        while q:
            num, score = q.popleft()
            ans = max(ans, score)
            for nei in g[num]:
                indeg[nei] -= 1
                dists[nei] = max(dists[nei], score)
                if indeg[nei] == 0:
                    q.append((nei, nei + dists[nei]))
        return ans % (10**9+7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        i, j, n, m = 0,0,len(nums1),len(nums2)
        a,b = 0,0
        result = 0
        while i<n or j<m:
            if i<n and (j==m or nums1[i]<nums2[j]):
                a+=nums1[i]
                i+=1
            elif j<m and (i==n or nums1[i]>nums2[j]):
                b+=nums2[j]
                j+=1
            else:
                a=b=max(a,b)+nums1[i]
                i+=1
                j+=1
        
        return max(a,b)%(10**9+7)


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        a = b = i = j = 0
        
        c = 0
        while(i < len(nums1) or j < len(nums2)):
            if(i < len(nums1) and (j == len(nums2) or nums1[i] < nums2[j])):
                a += nums1[i]
                i += 1
            elif(j < len(nums2) and (i == len(nums1) or nums2[j] < nums1[i])):
                b += nums2[j]
                j += 1
            else:
                c += max(a, b) + nums1[i]
                i += 1
                j += 1
                a = b = 0
        return (c + max(a, b)) % (10 ** 9 + 7)        


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        prev = collections.defaultdict(set)
        MOD = 10 ** 9 + 7
        if not nums1:
            return sum(nums2)
        elif not nums2:
            return sum(num1)
        ans = 0
        combined = sorted(set(nums1 + nums2))
        dp = collections.defaultdict(lambda: 0)
        dp[-1] = 0
        
        for i in  range(len(nums1)):
            if i == 0:
                prev[nums1[i]].add(-1)
            prev[nums1[i]].add(nums1[i - 1])
            
        for i in range(len(nums2)):
            if i == 0:
                prev[nums2[i]].add(-1)
            prev[nums2[i]].add(nums2[i - 1])
        
        for num in combined:
            for p in prev[num]:
                dp[num] = max(dp[p] + num, dp[num])
                ans = max(ans, dp[num])
        return ans % MOD


class Solution:
    def maxSum(self, A, B):
        i, j, n, m = 0, 0, len(A), len(B)
        a, b, mod = 0, 0, 10**9 + 7
        while i < n or j < m:
            if i < n and (j == m or A[i] < B[j]):
                a += A[i]
                i += 1
            elif j < m and (i == n or A[i] > B[j]):
                b += B[j]
                j += 1
            else:
                a = b = max(a, b) + A[i]
                i += 1
                j += 1
        return max(a, b) % mod

                
        
            
            


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int: 
        dp1, dp2 = collections.defaultdict(lambda: 0), collections.defaultdict(lambda: 0)
        i = j = 0
        
        while i < len(nums1) and j < len(nums2):
            x, y = nums1[i], nums2[j]
            if x < y:
                if i == 0:
                    dp1[x] = dp2[y] + x
                else:
                    dp1[x] = max(dp1[nums1[i-1]], dp2[y]) + x
                i += 1
            elif x > y:
                if j == 0:
                    dp2[y] = dp1[x] + y
                else:
                    dp2[y] = max(dp2[nums2[j-1]], dp1[x]) + y
                j += 1
            else:
                dp1[x] = max((dp2[nums2[j-1]] if j != 0 else 0) + x, (dp1[nums1[i-1]] if i != 0 else 0) + x)
                dp2[y] = max((dp1[nums1[i-1]] if i != 0 else 0) + y, (dp2[nums2[j-1]] if j != 0 else 0) + y)
                i += 1
                j += 1
            
        x, y = max(dp1.values()), max(dp2.values())
        
        while i < len(nums1):
            x += nums1[i]
            i += 1
            
        while j < len(nums2):
            y += nums2[j]
            j += 1
        
        return max(x, y) % (10 ** 9 + 7)


def findIndex(arr, ele, start, end) :
    
    while (start < end) :
        middle = (start + end - 1) // 2
        
        if ele == arr[middle] :
            return middle
        if ele < arr[middle] :
            end = middle
        elif ele > arr[middle] :
            start = middle + 1
    
    return -1
    
class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        temp, total = 0, 0
        i, j = 0, 0
        n1, n2 = len(nums1), len(nums2)
        path1, path2 = nums1, nums2
        
        while (i < n1) :
            index = findIndex(path2, path1[i], j, n2)
            if index == -1 :
                total += path1[i]
                temp += path1[i]
                i += 1
            else :
                if (temp >= sum(path2[j : index])) :
                    total += path1[i]
                    temp = path1[i]
                else :
                    total -= temp
                    total += sum(path2[j : index + 1])
                    temp = path2[index]
                i, j = index + 1, i
                n1, n2 = n2, n1
                path1, path2 = path2, path1
        
        if (temp < sum(path2[j : n2])) :
                total -= temp
                total += sum(path2[j : n2])
        return (total % 1000000007)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        common = set(nums1).intersection(set(nums2))
        ans = 0
        segments1 = [0]*(len(common)+1)
        
        tmp = 0
        j=0
        for i in nums1:
            tmp+=i
            if i in common:
                segments1[j] = tmp
                j+=1
                tmp = 0
        segments1[j] = tmp    
        
        j=0
        tmp = 0
        for i in nums2:
            tmp+=i
            if i in common:
                ans+=max(segments1[j], tmp)
                j+=1
                tmp = 0
        
        ans+=max(segments1[j], tmp)

        return ans % (10**9+7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        m=len(nums1);n=len(nums2);i=m-1;j=n-1;s1=0;s2=0
        while( i>=0 and j>=0):
            if(nums1[i]>nums2[j]):
                s1+=nums1[i];i-=1
            elif(nums2[j]>nums1[i]):
                s2+=nums2[j];j-=1
            else:
                s1=max(s1,s2)+nums1[i]
                s2=s1
                i-=1;j-=1
        if(i!=-1):s1+=sum(nums1[:i+1])
        if(j!=-1):s2+=sum(nums2[:j+1])
        return max(s1,s2)%(10**9+7)


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        prev = collections.defaultdict(set)
        MOD = 10 ** 9 + 7
        if not nums1:
            return sum(nums2)
        elif not nums2:
            return sum(num1)
        ans = 0
        
        dp = collections.defaultdict(lambda: 0)
        dp[-1] = 0
        
        for i in  range(len(nums1)):
            if i == 0:
                prev[nums1[i]].add(-1)
            prev[nums1[i]].add(nums1[i - 1])
            
        for i in range(len(nums2)):
            if i == 0:
                prev[nums2[i]].add(-1)
            prev[nums2[i]].add(nums2[i - 1])
        i = j = 0
        while i < len(nums1) or j < len(nums2):
            target = -1
            if j >= len(nums2) or (i < len(nums1) and nums1[i] < nums2[j]):
                target = nums1[i]
                i += 1
            else:
                target = nums2[j]
                j += 1
        
            for p in prev[target]:
                dp[target] = max(dp[p] + target, dp[target])
                ans = max(ans, dp[target])
        return ans % MOD


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        self.mod_value = pow(10, 9) + 7
        n = len(nums1)
        m = len(nums2)
        
        i = 0
        j = 0
        format_nums1 = []
        format_nums2 = []
        while i < n and j < m:
            if nums1[i] == nums2[j]:
                if len(format_nums1) == 0 or format_nums1[-1][1] == 0:
                    format_nums1.append([[0, 0], 1])
                if len(format_nums2) == 0 or format_nums2[-1][1] == 0:
                    format_nums2.append([[0, 0], 1])
                format_nums1.append([[0, nums1[i]], 0])
                format_nums2.append([[0, nums2[j]], 0])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                if len(format_nums1) == 0 or format_nums1[-1][1] == 0:
                    format_nums1.append([[0, nums1[i]], 1])
                else:
                    format_nums1[-1][0] = self.add_value(format_nums1[-1][0], nums1[i])
                i += 1
            else:
                if len(format_nums2) == 0 or format_nums2[-1][1] == 0:
                    format_nums2.append([[0, nums2[j]], 1])
                else:
                    format_nums2[-1][0] = self.add_value(format_nums2[-1][0], nums2[j])
                j += 1
        while i < n:
            if len(format_nums1) == 0 or format_nums1[-1][1] == 0:
                format_nums1.append([[0, nums1[i]], 1])
            else:
                format_nums1[-1][0] = self.add_value(format_nums1[-1][0], nums1[i])
            i += 1
        while j < m:
            if len(format_nums2) == 0 or format_nums2[-1][1] == 0:
                format_nums2.append([[0, nums2[j]], 1])
            else:
                format_nums2[-1][0] = self.add_value(format_nums2[-1][0], nums2[j])
            j += 1
        if format_nums1[-1][1] == 0:
            format_nums1.append([[0, 0], 1])
        if format_nums2[-1][1] == 0:
            format_nums2.append([[0, 0], 1])
        # print(format_nums1)
        # print(format_nums2)
        max_value1 = [0, 0]
        max_value2 = [0, 0]
        n = len(format_nums1)
        for i in range(n):
            if format_nums1[i][1] == 0 or i == 0:
                max_value1 = self.add_value_pair(max_value1, format_nums1[i][0])
                max_value2 = self.add_value_pair(max_value2, format_nums2[i][0])
            else:
                temp1 = self.add_value_pair(max_value2, format_nums1[i][0])
                temp2 = self.add_value_pair(max_value1, format_nums2[i][0])
                max_value1 = self.max(self.add_value_pair(max_value1, format_nums1[i][0]), temp1)
                max_value2 = self.max(self.add_value_pair(max_value2, format_nums2[i][0]), temp2)
                # max_value1 = self.add_value_pair(max_value1, format_nums1[i][0])
                # max_value2 = self.add_value_pair(max_value2, format_nums2[i][0])
        return self.max(max_value1, max_value2)[1]


    def add_value(self, value_pair, value):
        value_pair[1] += value
        while (value_pair[1] >= self.mod_value):
            value_pair[0] += 1
            value_pair[1] -= self.mod_value
        return value_pair

    def add_value_pair(self, value_pair1, value_pair2):
        result = [value_pair1[0] + value_pair2[0], value_pair1[1] + value_pair2[1]]
        while result[1] >= self.mod_value:
            result[0] += 1
            result[1] -= self.mod_value
        return result

    def max(self, value_pair1, value_pair2):
        if value_pair1[0] == value_pair2[0]:
            if (value_pair1[1] > value_pair2[1]):
                return value_pair1
        elif value_pair1[0] > value_pair2[0]:
            return value_pair1
        return value_pair2

import bisect 
from collections import defaultdict
mod = 10**9+7
class Solution:
    d_nums1 = defaultdict(int)
    d_nums2 = defaultdict(int)
    dp = []
    def f(self, nums1, nums2, ar_ind, pos):
        if self.dp[ar_ind][pos]!=-1:
            return self.dp[ar_ind][pos]
        if ar_ind == 1:
            if pos == len(nums2):
                 self.dp[ar_ind][pos] = 0 
            elif self.d_nums1[nums2[pos]] == 0 and nums1[0]!=nums2[pos]:
                self.dp[ar_ind][pos] = (nums2[pos] + self.f(nums1,nums2,1,pos+1))
            else:
                self.dp[ar_ind][pos] = (nums2[pos] + max(self.f(nums1,nums2,1,pos+1),self.f(nums1,nums2,0,self.d_nums1[nums2[pos]]+1)))
        else:
            if pos == len(nums1):
                self.dp[ar_ind][pos] =  0
            elif self.d_nums2[nums1[pos]] == 0 and nums2[0]!=nums1[pos]:
                self.dp[ar_ind][pos] =  (nums1[pos] + self.f(nums1,nums2,0,pos+1))
            else:
                self.dp[ar_ind][pos] = (nums1[pos] + max(self.f(nums1,nums2,0,pos+1),self.f(nums1,nums2,1,self.d_nums2[nums1[pos]]+1)))
        return self.dp[ar_ind][pos]
                
    
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        self.d_nums1.clear()
        self.d_nums2.clear()
        for i in range(len(nums1)):
            self.d_nums1[nums1[i]] = i 
        for i in range(len(nums2)):
            self.d_nums2[nums2[i]] = i 
        self.dp = [[-1]*(len(nums1)+1)]
        self.dp.append([-1]*(len(nums2)+1))
        # print(self.dp)
        self.f(nums1,nums2,1,0)
        self.f(nums1,nums2,0,0)
        
        # print(self.dp)
        return max(self.dp[0][0],self.dp[1][0])%mod

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        l1,l2=len(nums1),len(nums2)
        g=defaultdict(set)
        for i in range(1,l1): g[nums1[i-1]].add(nums1[i])
        for i in range(1,l2): g[nums2[i-1]].add(nums2[i])
        @lru_cache(None)
        def dfs(n):
            x=0
            for i in g[n]: x=max(x,dfs(i))
            return n+x
        res=max(dfs(nums1[0]),dfs(nums2[0]))
        return res%1000000007

class Solution:
    
    def binary_search(self,  arr, low, high, x): 
        # Check base case 
        if high >= low: 

            mid = (high + low) // 2
            #print(high, low, mid)
            #print(arr)
            # If element is present at the middle itself 
            if arr[mid] == x: 
                return mid 

            # If element is smaller than mid, then it can only 
            # be present in left subarray 
            elif arr[mid] > x: 
                return self.binary_search(arr, low, mid - 1, x) 
            # Else the element can only be present in right subarray 
            else: 
                return self.binary_search(arr, mid + 1, high, x) 
        else: 
            # Element is not present in the array 
            return -1
        
        
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        modulo = 1000000007
        num1Sum =0
        maxSum =0
        num2sum = 0
        startIndex = 0
        len2 = len(nums2)
        for num1 in nums1:
            num1InNum2 = self.binary_search(nums2, startIndex, len2-1, num1)
            #print(num1InNum2)
            if num1InNum2 != -1:
                num2sum =  sum(nums2[startIndex:num1InNum2])
                maxSum += num1Sum if num1Sum > num2sum else num2sum
                maxSum += num1
                num2sum = num1Sum = 0
                startIndex = num1InNum2 + 1
            else:
                num1Sum += num1
                
        num2sum = sum(nums2[startIndex:])
        maxSum += num1Sum if num1Sum > num2sum else num2sum
        num2sum = num1Sum = 0
        #print(maxSum)
        maxSum = maxSum % modulo
        return maxSum


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        ## RC ##
        ## APPROACH : GREEDY ##
        ## LOGIC ##
        ## 1. similar to merging 2 sorted arrays
        ## 2. Maintain sum for each array
        ## 3. when you find the same element in both arrays, only take maximum of sum1, sum2 and reset them
        
        p1, p2, sum1, sum2, result = 0, 0, 0, 0, 0
        while(p1 < len(nums1) and p2 < len(nums2)):
            if nums1[p1] == nums2[p2]:
                result += max(sum1, sum2) + nums1[p1]
                sum1, sum2 = 0, 0
                p1, p2 = p1 + 1, p2 + 1
            elif nums1[p1] < nums2[p2]:
                sum1 += nums1[p1]
                p1 += 1
            else:
                sum2 += nums2[p2]
                p2 += 1

        while(p1 < len(nums1)):
            sum1 += nums1[p1]
            p1 += 1

        while(p2 < len(nums2)):
            sum2 += nums2[p2]
            p2 += 1

        return (result + max(sum1 , sum2)) % (10**9 + 7)


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        a = 0; b = 0
        i = 0; j = 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]: a += nums1[i]; i+=1
            elif nums1[i] > nums2[j]: b += nums2[j]; j+=1
            else:
                a = b = max(a, b) + nums1[i];
                i+=1; j+=1

        while i < len(nums1): a += nums1[i]; i+=1
        while j < len(nums2): b += nums2[j]; j+=1
        return max(a, b) % 1_000_000_007


class Solution:
    def maxSum(self, A: List[int], B: List[int]) -> int:
        maxi = max(A[-1], B[-1])
        A.append(maxi + 1)
        B.append(maxi + 1)
        
        i = j = 0
        s1 = s2 = 0
        MOD = 10 ** 9 + 7
        while i < len(A) and j < len(B):
            if A[i] < B[j]:
                s1 += A[i]
                i += 1
            elif A[i] > B[j]:
                s2 += B[j]
                j += 1
            else:
                s1 = s2 = (max(s1, s2) + A[i]) % MOD
                i += 1
                j += 1
        return (MOD + s1 - A[-1]) % MOD
        
    
    def maxSum_foolish_DP(self, A: List[int], B: List[int]) -> int:
        N = [A, B]
        NN = [{v : i for i, v in enumerate(A)}, {v : i for i, v in enumerate(B)}]

        @functools.lru_cache(None)
        def helper(index, is_bottom, changed):
            nonlocal N, NN
            if index < 0:
                return 0

            value = N[is_bottom][index]
            if changed:
                if value not in NN[1 ^ is_bottom]:
                    return float('-inf')
                return helper(NN[1 ^ is_bottom][value], 1 ^ is_bottom, 0)
            else:
                return value + max(helper(index - 1, is_bottom, 0), helper(index - 1, is_bottom, 1))
        
        return (max(helper(len(A) - 1, 0, 0), helper(len(A) - 1, 0, 1), helper(len(B) - 1, 1, 0), helper(len(B) - 1, 1, 1))) % (10 ** 9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        a = 0; b = 0
        i = 0; j = 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]: a += nums1[i]; i+=1
            elif nums1[i] > nums2[j]: b += nums2[j]; j+=1
            else:
                a = b = max(a, b) + nums1[i] # they are equal when numbers are equal
                i+=1; j+=1

        while i < len(nums1): a += nums1[i]; i+=1
        while j < len(nums2): b += nums2[j]; j+=1
        return max(a, b) % 1_000_000_007


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        cross = []
        n,m = len(nums1),len(nums2)
        i,j = 0,0
        M = 10**9 + 7
        while i < n and j < m:
            if nums1[i] > nums2[j]:
                j += 1
            elif nums2[j] > nums1[i]:
                i += 1
            else:
                cross.append((i,j))
                i += 1
                j += 1
        l = len(cross)
        if l == 0:
            return max(sum(nums1),sum(nums2)) % M
        ans = max(sum(nums1[cross[-1][0]:]),sum(nums2[cross[-1][1]:]))
        ans %= M
        for i in range(l-2,-1,-1):
            ans += max(sum(nums1[cross[i][0]:cross[i+1][0]]),sum(nums2[cross[i][1]:cross[i+1][1]])) 
            ans %= M
        ans += max(sum(nums1[:cross[0][0]]),sum(nums2[:cross[0][1]])) 
        ans %= M
        return ans % M
#         memo = {}
#         def fun(cl,f):
#             if (cl,f) in memo:
#                 return memo[(cl,f)]
#             if cl == l-1:
#                 if f == 0:
#                     return sum(nums1[cross[cl][0]:])
#                 else:
#                     return sum(nums2[cross[cl][1]:])


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        sumMax = 0
        nLen1 = len(nums1)
        nLen2 = len(nums2)        
        loopLen = min(nLen1, nLen2)
        
        maxVal = (10**9) + 7
        
        idx1 = {nums1[0]:0}
        idx2 = {nums2[0]:0}
        ps1 = 0
        ps2 = 0
        pe1 = 1
        pe2 = 1
        for i in range(1, loopLen):
            v1 = nums1[i]
            v2 = nums2[i]
            sumT = 0
            if v1 == v2:
                pe1 = i + 1
                pe2 = i + 1
                sum1 = sum(nums1[ps1:pe1])
                sum2 = sum(nums2[ps2:pe2])
                sumT = max(sum1, sum2)
                ps1 = pe1
                ps2 = pe2
            if v1 in idx2:
                pe1 = i + 1
                pe2 = idx2[v1] + 1
                sum1 = sum(nums1[ps1:pe1])
                sum2 = sum(nums2[ps2:pe2])
                sumT = max(sum1, sum2)
                ps1 = pe1
                ps2 = pe2
            elif v2 in idx1:
                pe2 = i + 1
                pe1 = idx1[v2] + 1
                sum1 = sum(nums1[ps1:pe1])
                sum2 = sum(nums2[ps2:pe2])
                sumT = max(sum1, sum2)
                ps1 = pe1
                ps2 = pe2
            
            # print(i, ps1, pe1, ps2, pe2, sumT)
            sumMax += sumT
            sumMax = sumMax % maxVal
            
            idx1[v1] = i
            idx2[v2] = i
            
        if nLen1 > nLen2:
            for i in range(loopLen,nLen1):
                v1 = nums1[i]
                if v1 in idx2:
                    pe1 = i + 1
                    pe2 = idx2[v1] + 1
                    sum1 = sum(nums1[ps1:pe1])
                    sum2 = sum(nums2[ps2:pe2])
                    sumT = max(sum1, sum2)
                    ps1 = pe1
                    ps2 = pe2
                else:
                    sumT = 0
                sumMax += sumT
                sumMax = sumMax % maxVal
                idx1[v1] = i
                
                if v1 > nums2[-1]:
                    break
        elif nLen2 > nLen1:
            for i in range(loopLen,nLen2):
                v2 = nums2[i]
                if v2 in idx1:
                    pe2 = i + 1
                    pe1 = idx1[v2] + 1
                    sum1 = sum(nums1[ps1:pe1])
                    sum2 = sum(nums2[ps2:pe2])
                    sumT = max(sum1, sum2)
                    ps1 = pe1
                    ps2 = pe2
                else:
                    sumT = 0
                # print(i, ps1, pe1, ps2, pe2, sumT)
                sumMax += sumT
                sumMax = sumMax % maxVal
                idx2[v2] = i
                
                if v2 > nums1[-1]:
                    break
                    
        # print(ps1, ps2)
        if(ps1 < nLen1):
            sum1 = sum(nums1[ps1:])
        else:
            sum1 = 0
        
        if(ps2 < nLen2):
            sum2 = sum(nums2[ps2:])
        else:
            sum2 = 0
            
        sumT = max(sum1, sum2)
        sumMax += sumT
        sumMax = sumMax % maxVal
        return sumMax

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        M, N = len(nums1), len(nums2)
        sum1, sum2 = 0, 0
        i, j = 0, 0
        res = 0
        while i < M and j < N:
            if nums1[i] < nums2[j]:
                sum1 += nums1[i]
                i += 1
            elif nums1[i] > nums2[j]:
                sum2 += nums2[j]
                j += 1
            else:
                res += max(sum1, sum2) + nums1[i]
                i += 1
                j += 1
                sum1 = 0
                sum2 = 0
                
        while i < M:
            sum1 += nums1[i]
            i += 1
        while j < N:
            sum2 += nums2[j]
            j += 1
        return (max(sum1, sum2) + res) % (10 ** 9 + 7)
                


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        M,N = len(nums1),len(nums2)
        i = 0
        j = 0
        sum1 = 0
        sum2 = 0
        res = 0
        while i < M and j < N:
            if nums1[i] < nums2[j]:
                sum1 += nums1[i]
                i += 1
                
            elif nums1[i] > nums2[j]:
                sum2 += nums2[j]
                j += 1
            else:
                res += max(sum1,sum2) + nums1[i]
                i += 1
                j += 1
                sum1 = 0
                sum2 = 0
            
        while i < M:
            sum1 += nums1[i]
            i += 1
            
        while j < N:
            sum2 += nums2[j]
            j += 1
        return (res + max(sum1,sum2)) % (10 ** 9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        n1,n2 = nums1,nums2
        s,t,sum1,sum2 = len(n1)-1,len(n2)-1,0,0
        li = []
        ans = 0
        while s >= 0 and t >= 0:
            if n1[s] > n2[t]:
                sum1 += n1[s]
                s -= 1
            elif n1[s] < n2[t]:
                sum2 += n2[t]
                t -= 1
            else:
                ans += max(sum1+n1[s],sum2+n1[s])
                # li.append((sum1+n1[s],sum2+n1[s]))
                sum1 = sum2 = 0
                s -= 1
                t -= 1
        if s >= 0: ans += max(sum1+sum(n1[:s+1]),sum2)
            # li.append((sum1+sum(n1[:s+1]),sum2))
        if t >= 0: ans += max(sum1,sum2+sum(n2[:t+1]))
            # li.append((sum1,sum2+sum(n2[:t+1])))
        # ans = 0
        # for l in li:
        #     ans += max(l[0],l[1])
        #     ans = ans % (10**9+7)
        return ans  % (10**9+7)

class Solution:
    def maxSum(self, A: List[int], B: List[int]) -> int:
        i = j = 0
        s1 = s2 = 0
        MOD = 10 ** 9 + 7
        while i < len(A) or j < len(B):
            if i < len(A) and (j == len(B) or A[i] < B[j]):
                s1 += A[i]
                i += 1
            elif j < len(B) and (i == len(A) or A[i] > B[j]):
                s2 += B[j]
                j += 1
            else:
                s1 = s2 = (max(s1, s2) + A[i]) % MOD
                i += 1
                j += 1
        return max(s1, s2) % MOD
        
    
    def maxSum_foolish_DP(self, A: List[int], B: List[int]) -> int:
        N = [A, B]
        NN = [{v : i for i, v in enumerate(A)}, {v : i for i, v in enumerate(B)}]

        @functools.lru_cache(None)
        def helper(index, is_bottom, changed):
            nonlocal N, NN
            if index < 0:
                return 0

            value = N[is_bottom][index]
            if changed:
                if value not in NN[1 ^ is_bottom]:
                    return float('-inf')
                return helper(NN[1 ^ is_bottom][value], 1 ^ is_bottom, 0)
            else:
                return value + max(helper(index - 1, is_bottom, 0), helper(index - 1, is_bottom, 1))
        
        return (max(helper(len(A) - 1, 0, 0), helper(len(A) - 1, 0, 1), helper(len(B) - 1, 1, 0), helper(len(B) - 1, 1, 1))) % (10 ** 9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        score = 0
        total1 = 0
        total2 = 0
        pos1 = 0
        pos2 = 0
        
        
        while pos1 < len(nums1) or pos2 < len(nums2):
            if pos1 < len(nums1) and (pos2 >= len(nums2) or nums1[pos1] < nums2[pos2]):
                total1+=nums1[pos1]
                pos1+=1
                continue
            
            if pos2 < len(nums2) and (pos1 >= len(nums1) or nums1[pos1] > nums2[pos2]):
                total2+=nums2[pos2]
                pos2+=1
                continue
                
            score+=nums1[pos1] + max(total1, total2)
                
            pos1+=1
            pos2+=1
            total1 = 0
            total2 = 0
            
        score += max(total1, total2)
                
        return score % ( 10**9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        n1,n2 = nums1,nums2
        s,t,sum1,sum2 = len(n1)-1,len(n2)-1,0,0
        ans = 0
        while s >= 0 and t >= 0:
            if n1[s] > n2[t]:
                sum1 += n1[s]
                s -= 1
            elif n1[s] < n2[t]:
                sum2 += n2[t]
                t -= 1
            else:
                ans += max(sum1+n1[s],sum2+n1[s])
                sum1 = sum2 = 0
                s -= 1
                t -= 1
        if s >= 0: ans += max(sum1+sum(n1[:s+1]),sum2)
        if t >= 0: ans += max(sum1,sum2+sum(n2[:t+1]))
        return ans  % (10**9+7)

class Solution:
    def maxSum(self, A: List[int], B: List[int]) -> int:
        i, j, n, m = 0, 0, len(A), len(B)
        a, b, mod = 0, 0, 10**9 + 7
        while i < n or j < m:
            if i < n and (j == m or A[i] < B[j]):
                a += A[i]
                i += 1
            elif j < m and (i == n or A[i] > B[j]):
                b += B[j]
                j += 1
            else:
                a = b = max(a, b) + A[i]
                i += 1
                j += 1
        return max(a, b) % mod

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        dp=collections.defaultdict(int)
        i,j=len(nums1)-2,len(nums2)-2
        dp[nums1[-1]]=nums1[-1]
        dp[nums2[-1]]=nums2[-1]
        while i>=0 or j>=0:
            v1,v2=nums1[i] if i>=0 else -1,nums2[j] if j>=0 else -1
            # print(i,j,v1,v2,dp)
            if v1>v2:
                dp[v1]=v1+dp[nums1[i+1]]
                i-=1
            elif v1<v2:
                dp[v2]=v2+dp[nums2[j+1]]
                j-=1
            else:
                dp[v1]=v1+max(dp[nums1[i+1]],dp[nums2[j+1]])
                i-=1
                j-=1
        return max(dp[nums1[0]],dp[nums2[0]])%1000000007
            
        


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        ans, a, b = 0, 0, 0
        n1, n2 = len(nums1), len(nums2)
        i, j = 0, 0
        while i<n1 and j<n2:
            if nums1[i] == nums2[j]:
                ans += max(a,b) + nums1[i]
                i+=1; j+=1
                a,b=0,0
            elif nums1[i] < nums2[j]:
                a+=nums1[i]
                i+=1
            else:
                b+=nums2[j]
                j+=1
        while i<n1:
            a+=nums1[i]
            i+=1
        while j<n2:
            b+=nums2[j]
            j+=1
        ans +=  max(a,b)
        return ans % (10**9 + 7)
            


class Solution:
    def maxSum(self, nums1, nums2):
        M, N = len(nums1), len(nums2)
        sum1, sum2 = 0, 0
        i, j = 0, 0
        res = 0
        
        while i < M and j < N:
            if nums1[i] < nums2[j]:
                sum1 += nums1[i]
                i += 1
            elif nums1[i] > nums2[j]:
                sum2 += nums2[j]
                j += 1
            else:
                res += max(sum1, sum2) + nums1[i]
                i += 1
                j += 1
                sum1 = 0
                sum2 = 0
                
        while i < M:
            sum1 += nums1[i]
            i += 1
        while j < N:
            sum2 += nums2[j]
            j += 1
        return (res + max(sum1, sum2)) % 1000000007


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        M,N = len(nums1),len(nums2)
        i = 0
        j = 0
        res = sum1 = sum2 = 0
        while i < M and j < N:
            if nums1[i] < nums2[j]:
                sum1 += nums1[i]
                i += 1
            elif nums1[i] > nums2[j]:
                sum2 += nums2[j]
                j += 1
            else:
                res += max(sum1,sum2) + nums1[i]
                i += 1
                j += 1
                sum1 = sum2 = 0
                
        while i < M:
            sum1 += nums1[i]
            i += 1
            
        while j < N:
            sum2 += nums2[j]
            j += 1
        return (res + max(sum1,sum2)) % (10 ** 9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        accu1 = list(accumulate(nums1))
        accu2 = list(accumulate(nums2))
        print(accu1)
        ans  = i = j = 0
        pi = pj = -1
        while i<len(nums1) and j<len(nums2):
            if nums1[i]<nums2[j]:
                i+=1
            elif nums1[i]>nums2[j]:
                j+=1
            else:
                ans+=max(accu1[i], accu2[j]) if pi<0 else max(accu1[i]-accu1[pi], accu2[j]-accu2[pj]) 
                pi,pj,i,j = i,j,i+1,j+1
        
        ans+=max(accu1[-1], accu2[-1]) if pi<0 else max(accu1[-1]-accu1[pi], accu2[-1]-accu2[pj]) 
        
        return ans % (10**9+7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        # [idxnums1,idxnums2,value]
        changeSum = 0
        partial1, partial2 = 0,0
        i,j=0,0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                print((partial1,partial2))
                changeSum = (changeSum + nums1[i] + max(partial1, partial2)) % (10**9 + 7)
                i += 1
                j += 1
                partial1, partial2 = 0,0
            elif nums1[i] < nums2[j]:
                partial1 += nums1[i]
                i += 1
            else:
                partial2 += nums2[j]
                j += 1
        while i < len(nums1):
            partial1 += nums1[i]
            i += 1
        while j < len(nums2):
            partial2 += nums2[j]
            j += 1
        changeSum = (changeSum + max(partial1, partial2)) % (10**9 + 7)
            
        return changeSum % (10**9 + 7)
                


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n = len(nums2)
        mod = 10**9+7
        pre1 = [0] * (m+1)
        pre2 = [0] * (n+1)
        
        for i in range(m):
            pre1[i+1] = pre1[i] + nums1[i]
        for i in range(n):
            pre2[i+1] = pre2[i] + nums2[i]
        
        cm1 = []
        cm2 = []
        st = set()
        d = {}
        for i in range(m):
            d[nums1[i]] = i
        st1 = set(nums1)   
        # print(st)
        for i in range(n):
            if nums2[i] in st1:
                cm1.append(d[nums2[i]])
                cm2.append(i)
        ans = 0
        # print(pre1,pre2,cm1,cm2)
        for i in range(len(cm1)):
            idx1 = cm1[i]
            idx2 = cm2[i]
            
            if i == 0:
                sm1 = pre1[idx1]
                sm2 = pre2[idx2]
            else:
                sm1 = pre1[idx1] - pre1[cm1[i-1]+1]
                sm2 = pre2[idx2] - pre2[cm2[i-1]+1]
            ans += max(sm1,sm2)
            ans %= mod
        op1 = 0
        op2 = 0
        if len(cm1) and cm1[-1]+1 < m:
            op1 = sum(nums1[cm1[-1]+1:])
        if len(cm2) and cm2[-1]+1 < n:
            op2 = sum(nums2[cm2[-1]+1:])
        if not len(cm1):
            return (max(sum(nums1),sum(nums2))) %mod
        ans += max(op1,op2)
        ans %= mod
        return (ans+sum(nums1[i] for i in cm1)) % mod
                


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        one = 0
        two = 0
        i = 0 
        j = 0
        while(i<len(nums1) and j<len(nums2)):
            if(nums1[i]==nums2[j]):
                one = two =  max(one,two)+nums1[i]
                i+=1
                j+=1
            elif(nums1[i]>nums2[j]):
                two+=nums2[j]
                j+=1
            else:
                one+=nums1[i]
                i+=1
                
        # print(i,j)
        while(i<len(nums1)):
            one+=nums1[i]
            i+=1
        while(j<len(nums2)):
            two+=nums2[j]
            j+=1
            
            
        return max(one,two)%1000000007
            
            
            


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        dp1 = [0]*(len(nums1)+1)
        dp2 = [0]*(len(nums2)+1)
        
        dp1[-1] = 0
        dp2[-1] = 0
        
        to1 = {}
        to2 = {}
        inds2 = {y: j for j, y in enumerate(nums2)}
        for i, x in enumerate(nums1):
            if x in inds2:
                to2[i] = inds2[x]
                to1[inds2[x]] = i
        
        # print(dp1, dp2, to2, to1)
        
        i = len(nums1)-1
        j = len(nums2)-1
        
        while i >= 0 and j >= 0:
            if i not in to2:
                dp1[i] = nums1[i] + dp1[i+1]
                i -= 1
            elif j not in to1:
                dp2[j] = nums2[j] + dp2[j+1]
                j -= 1
            else:
                dp1[i] = dp2[j] = nums1[i] + max(dp1[i+1], dp2[j+1])
                i -= 1
                j -= 1
        
        # print(dp1, dp2)
        while i >= 0:
            dp1[i] = nums1[i] + dp1[i+1]
            i -= 1
                
        while j >= 0:
            dp2[j] = nums2[j] + dp2[j+1]
            j -= 1
        
        # print(dp1, dp2)
        
        return max(dp1[0], dp2[0]) % (10**9 + 7)


MOD = 1000000007
class Solution:
    def maxSum(self, nums1, nums2):
        sum1, sum2, res = 0, 0, 0
        p1, p2 = 0, 0
        while p1 <= len(nums1) - 1 and p2 <= len(nums2) - 1:
            if nums1[p1] == nums2[p2]:
                res += max(sum1, sum2) + nums1[p1]
                sum1, sum2 = 0, 0
                p1 += 1
                p2 += 1
            elif nums1[p1] < nums2[p2]:
                sum1 += nums1[p1]
                p1 += 1
            else:
                sum2 += nums2[p2]
                p2 += 1
        if p1 <= len(nums1) - 1:
            sum1 += sum(nums1[p1:])
        if p2 <= len(nums2) - 1:
            sum2 += sum(nums2[p2:])
        return (res + max(sum1, sum2)) % MOD

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        N1 = len(nums1)
        N2 = len(nums2)
        
        dp1 = [0 for _ in range(N1 + 1)]
        dp2 = [0 for _ in range(N2 + 1)]
        
        i = 1
        j = 1
        
        while i < N1 + 1 and j < N2 + 1:
            if nums1[i - 1] == nums2[j - 1]:
                dp1[i] = max(dp1[i - 1], dp2[j - 1]) + nums1[i - 1]
                dp2[j] = max(dp1[i - 1], dp2[j - 1]) + nums2[j - 1]
                i += 1
                j += 1
            elif nums1[i - 1] < nums2[j - 1]:
                dp1[i] = dp1[i - 1] + nums1[i - 1]
                i += 1
            else:
                dp2[j] = dp2[j - 1] + nums2[j - 1]
                j += 1
            
        while i < N1 + 1:
            dp1[i] = dp1[i - 1] + nums1[i - 1]
            i += 1
            
        while j < N2 + 1:
            dp2[j] = dp2[j - 1] + nums2[j - 1]
            j += 1
            
        return max(dp1[-1], dp2[-1]) % (10 ** 9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        p1 = p2 = 0
        mx1 = 0 
        mx2 = 0
        while p1 < len(nums1) and p2 < len(nums2):
            if nums1[p1] == nums2[p2]:
                mx1 = mx2 = max(mx1, mx2) + nums1[p1]
                p1 += 1
                p2 += 1
            while p1 < len(nums1) and p2 < len(nums2) and nums1[p1] < nums2[p2]:
                mx1 += nums1[p1]
                p1 += 1
            while p1 < len(nums1) and p2 < len(nums2) and nums2[p2] < nums1[p1]:
                mx2 += nums2[p2]
                p2 += 1
            
        while p1 < len(nums1):
            mx1 += nums1[p1]
            p1 += 1
        while p2 < len(nums2):
            mx2 += nums2[p2]
            p2 += 1
        return max(mx1,mx2) % (10**9+7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        '''
        nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
        
        dp1:[30,28,23,18,10, 0]
        dp2: [28,24,18,9, 0]
        
        dp1[i] = if nums1[i]==nums2[j]: max(nums1[i]+dp1[i+1], nums1[i]+dp2[j+1])
                    else: nums1[i]+dp1[i+1]
        (dp1[len(nums1)]=0)
        dp2[i] = if nums1[j]==nums2[i]: max(nums1[i]+dp1[j+1], nums1[i]+dp2[i+1])
        
        i1, i2 = len(nums1)-1, len(nums2)-1
        while i1>=0 and i2>=0:
            if nums1[i1] == nums[i2]:
                dp1[i1] = max(nums1[i1]+dp1[i1+1], nums1[i2]+dp2[i2+1])
                i1-=1
                i2-=1
            elif nums1[i1] > nums[i2]:
                dp1[i1] = nums1[i1]+dp1[i1+1]
                i1-=1
            else:
                dp2[i2] = nums2[i2]+dp2[i2+1]
                i2-=1
        if i1>=0:
            return max(sum()+dp1[i1+1], dp2[i2+1])
            
        '''
        dp1 = [0 for _ in range(len(nums1)+1)]
        dp2 = [0 for _ in range(len(nums2)+1)]
        i1, i2 = len(nums1)-1, len(nums2)-1
        while i1>=0 and i2>=0:
            if nums1[i1] == nums2[i2]:
                dp1[i1] = max(nums1[i1]+dp1[i1+1], nums2[i2]+dp2[i2+1])
                dp2[i2] = max(nums1[i1]+dp1[i1+1], nums2[i2]+dp2[i2+1])
                i1-=1
                i2-=1
            elif nums1[i1] > nums2[i2]:
                dp1[i1] = nums1[i1]+dp1[i1+1]
                i1-=1
            else:
                dp2[i2] = nums2[i2]+dp2[i2+1]
                i2-=1
        # print(dp1)
        # print(dp2)
        if i1>=0:
            return max(sum(nums1[:i1+1])+dp1[i1+1], dp2[i2+1])%(10**9+7)
        else:
            return max(sum(nums2[:i2+1])+dp2[i2+1], dp1[i1+1])%(10**9+7)


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        sum1, sum2 = 0, 0
        index1, index2 = 0, 0
        len1, len2 = len(nums1), len(nums2)
        
        while index1 < len1 or index2 < len2:
            if index1 < len1 and (index2 == len2 or nums1[index1] < nums2[index2]):
                sum1 += nums1[index1]
                index1 += 1
            elif index2 < len2 and (index1 == len1 or nums1[index1] > nums2[index2]):
                sum2 += nums2[index2]
                index2 += 1
            else:
                sum1 = sum2 = max(sum1, sum2) + nums1[index1]
                index1 += 1
                index2 += 1
        
        return max(sum1, sum2) % (10**9+7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        sum1 = 0
        sum2 = 0
        i1 = len(nums1) - 1
        i2 = len(nums2) - 1
        paths = []
        while i1 >= 0 and i2 >= 0:
          if nums1[i1] > nums2[i2]:
            sum1 += nums1[i1]
            i1 -= 1
          elif nums1[i1] < nums2[i2]:
            sum2 += nums2[i2]
            i2 -= 1
          else:
            paths.append((sum1 + nums1[i1], sum2 + nums1[i1]))
            sum1 = sum2 = 0
            i1 -= 1
            i2 -= 1
        if i1 >= 0:
          paths.append((sum1 + sum(nums1[:i1+1]), sum2))
        if i2 >= 0:
          paths.append((sum1, sum2 + sum(nums2[:i2+1])))
        
        ans = 0
        for l, r in paths:
          ans += max(l, r)
          ans %= 10**9 + 7
        return ans      
            

        
        # print(nums1)
        # print(nums2)
        # print('')
        def _dp(ii, its1, val):
          # print(ii, its1, val)
          nums = nums1 if its1 else nums2
          oums = nums2 if its1 else nums1
          if ii == len(nums):
            return val
          # path.append((its1, nums[ii]))
          if nums[ii] in oums:
            ix = oums.index(nums[ii])
            # path.append((not its1, nums[ii]))
            opt = _dp(ix + 1, not its1, val + nums[ii])
          else:
            opt = 0
          cur = _dp(ii + 1,     its1, val + nums[ii]) 
          return max([opt, cur])
            
        
        return max([_dp(0, True, 0), _dp(0, False, 0)])
      


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        MOD = 10**9 + 7.
        # get the max array by intertweenin the two
        def csums(nums):
            arr = [None] * len(nums)
            for i in range(len(nums)): 
                prev = 0 if i == 0 else arr[i-1]
                arr[i] = prev + nums[i]
            return arr
        s1, s2 = csums(nums1), csums(nums2)
        mp1 = {v: idx for idx, v in enumerate(nums1)}
        mp2 = {v: idx for idx, v in enumerate(nums2)}
        sps = sorted(set(mp1.keys()) & set(mp2.keys())) # switch points
        ans = 0
        if not sps: 
            ans =  max(s1[-1], s2[-1]) % MOD
        else: 
            idx1 = idx2 = None
            for idx, sp in enumerate(sps): 
                idx1, idx2 = mp1[sp], mp2[sp]
                sum1 = s1[idx1] - (0 if idx == 0 else s1[mp1[sps[idx-1]]])
                sum2 = s2[idx2] - (0 if idx == 0 else s2[mp2[sps[idx-1]]])
                ans = (ans + max(sum1, sum2)) % MOD # can choose either one
            
            left1 = s1[-1] - s1[idx1]
            left2 = s2[-1] - s2[idx2]
            
            ans += max(left1, left2)
        return int(ans % MOD)

            
        
            
        
        
        
        
        
        
        
        
        
        
            
        
            
            
            
            
        
        
        


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        
        intersecting_index=[]
        
        l=0
        m=0
        
        while l<len(nums1) and m<len(nums2):
            if nums1[l]==nums2[m]:
                intersecting_index.append([l,m])
                l+=1
                m+=1
            elif nums1[l]>nums2[m]:
                m+=1
            else:
                l+=1
        
        prefix_1=[0 for i in range(len(nums1)+1)]
        prefix_2=[0 for i in range(len(nums2)+1)]
        for i in range(1,len(nums1)+1):
            prefix_1[i]=prefix_1[i-1]+nums1[i-1]
        for i in range(1,len(nums2)+1):
            prefix_2[i]=prefix_2[i-1]+nums2[i-1]
        
        
        ans=[]
        prev_1=0
        prev_2=0
        for i in intersecting_index:
            ans.append([prefix_1[i[0]+1]-prefix_1[prev_1] , prefix_2[i[1]+1]-prefix_2[prev_2]])
            prev_1=i[0]+1
            prev_2=i[1]+1
        
        ans.append([prefix_1[-1]-prefix_1[prev_1] , prefix_2[-1]-prefix_2[prev_2]])
        
        s=0
        for i in ans:
            s=(max(i[0],i[1])+s)%(pow(10,9)+7)
        return s
            
        
            


class Solution:
    def maxSum(self, l1: List[int], l2: List[int]) -> int:
        last_p1 = 0
        last_p2 = 0
        p1 = 0
        p2 = 0
        sum_so_far = 0
        while (p1 < len(l1) and p2 < len(l2) and last_p1 < len(l1) and last_p2 < len(l2)):
            if l1[p1] < l2[p2]:
                p1 += 1
            elif l1[p1] > l2[p2]:
                p2 += 1
            else: # ==
                sum_so_far += max(sum(l1[last_p1:p1]), sum(l2[last_p2:p2]))
                sum_so_far += l1[p1]
                last_p1 = p1 + 1
                last_p2 = p2 + 1
                p1 += 1
                p2 += 1

        if l1[-1] != l2[-1]:
            sum_so_far += max(sum(l1[last_p1:]), sum(l2[last_p2:]))
        return sum_so_far % 1000000007

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        mod=10**9+7
        l1=[]
        d={}
        d1={}
        d2={}
        
        for i in nums1:
            d[i]=1
        for i in nums2:
            d[i]=d.get(i,0)+1
        for i in d:
            if d[i]==2:
                l1.append(i)
                
        l1.sort()
        n1=len(l1)+1
        l1.insert(0,0)
        
        dp=[[0 for j in range(2)] for i in range(n1+1)]
        pref1=[0]*(len(nums1)+1)
        pref2=[0]*(len(nums2)+1)
        
        for i in range(len(nums1)):
            d1[nums1[i]]=i
            pref1[i+1]=pref1[i]+nums1[i]
        
        for i in range(len(nums2)):
            d2[nums2[i]]=i
            pref2[i+1]=pref2[i]+nums2[i]
        #print(d1,d2)
        d1[0]=0
        d2[0]=0
        for i in range(1,n1):
            
            dp[i][0]=max(dp[i-1][0],dp[i-1][1])+pref1[d1[l1[i]]+1]-pref1[d1[l1[i-1]]]-l1[i-1]
            dp[i][1]=max(dp[i-1][0],dp[i-1][1])+pref2[d2[l1[i]]+1]-pref2[d2[l1[i-1]]]-l1[i-1]
            #print(123,l1[i],dp[i][0],dp[i][1])
        #print(l1)
        return (max(dp[n1-1][0],dp[n1-1][1])+max(pref1[len(nums1)]-pref1[d1[l1[-1]]]-l1[-1],pref2[len(nums2)]-pref2[d2[l1[-1]]]-l1[-1]))%mod

from functools import lru_cache
class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        d = {
            0: {x:i for i, x in enumerate(nums1)},
            1: {x:i for i, x in enumerate(nums2)},
        }
        arrs = [nums1, nums2]
        MOD = 10 ** 9 + 7

        @lru_cache(None)
        def dp(i, j):
            res = 0
            while j < len(d[i]):
                val = arrs[i][j]
                if val not in d[1-i]:
                    res += val
                else:
                    k = d[1-i][val]
                    res += val + max(dp(1-i, k+1), dp(i, j+1)) 
                    return res
                j += 1
            return res
        return max(dp(0, 0), dp(1, 0)) % MOD

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        # Represents the max value (looking ahead) from this node 
        dp1 = [0 for _ in range(len(nums1))] + [0]
        dp2 = [0 for _ in range(len(nums2))] + [0]
        
        nums1.append(0)
        nums2.append(0)
        
        for i in range(len(nums1)-2, -1, -1):
            dp1[i] = (dp1[i+1] + nums1[i+1])
            
        for i in range(len(nums2)-2, -1, -1):
            dp2[i] = (dp2[i+1] + nums2[i+1])
            
        i, j = len(nums1)-2, len(nums2)-2
        
        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                dp1[i] = (nums1[i+1] + dp1[i+1])
                i -= 1
            elif nums1[i] < nums2[j]:
                dp2[j] = (nums2[j+1] + dp2[j+1])
                j -= 1
            else:
                # Find which one has the greater parent
                max_value = max(dp1[i+1] + nums1[i+1], dp2[j+1] + nums2[j+1])
                dp1[i] = max_value
                dp2[j] = max_value
                    
                j -= 1
                i -= 1
                
        while i >= 0:
            dp1[i] = (nums1[i+1] + dp1[i+1])
            i -= 1
            
        while j >= 0:
            dp2[j] = (nums2[j+1] + dp2[j+1])
            j -= 1
            
        return max((dp1[0] + nums1[0]) % (10**9 + 7), (dp2[0] + nums2[0]) % (10**9 + 7)) 

class Solution:
    def maxSum(self, A, B):
        i, j, n, m = 0, 0, len(A), len(B)
        a, b, mod = 0, 0, 10**9 + 7
        while i < n or j < m:
            if i < n and (j == m or A[i] < B[j]):
                a += A[i]
                i += 1
            elif j < m and (i == n or A[i] > B[j]):
                b += B[j]
                j += 1
            else:
                a = b = max(a, b) + A[i]
                i += 1
                j += 1
        return max(a, b) % mod


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        
        H1={}
        H2={}
        for i in range(len(nums1)):
            H1[nums1[i]]=i
        for i in range(len(nums2)):
            H2[nums2[i]]=i
    
        S1=set(H1.keys())
        S2=set(H2.keys())
        C=sorted(list(S1.intersection(S2)))
        if len(C)==0:
            return max(sum(nums1),sum(nums2))
#        print (C)
        ind1=ind2=0
        n1=[]
        n2=[]
        n=0
        for i in C:            
            i1=H1[i]+1
            i2=H2[i]+1
            n+=max(sum(nums1[ind1:i1]),sum(nums2[ind2:i2])) 

            n1.append(sum(nums1[ind1:H1[i]+1]))
            n2.append(sum(nums2[ind2:H2[i]+1]))
#            print(n1,n2)
            ind1=H1[i]+1
            ind2=H2[i]+1
        n1.append(sum(nums1[ind1:]))
        n2.append(sum(nums2[ind2:]))
        n+=max(sum(nums1[ind1:]),sum(nums2[ind2:]))
#        print (n1,n2)        
        return n % 1000000007        


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        N = len(nums1)
        M = len(nums2)
        
        def get_pos(nums):
            pos = defaultdict(lambda: -1)
            for i, x in enumerate(nums):
                pos[x] = i
            return pos
                
        pos1 = get_pos(nums1)
        pos2 = get_pos(nums2)
        
        dp1 = [0] * (N + 1)
        dp2 = [0] * (M + 1)
        i, j = N - 1, M - 1
        while i >= 0 or j >= 0:
            while i >= 0 and pos2[nums1[i]] < 0:
                dp1[i] = nums1[i] + dp1[i + 1]
                i -= 1
                
            while j >= 0 and pos1[nums2[j]] < 0:
                dp2[j] = nums2[j] + dp2[j + 1]
                j -= 1
                
            if i >= 0:
                p = pos2[nums1[i]]
                dp1[i] = nums1[i] + max(dp1[i + 1], dp2[p + 1])
                i -= 1
                
            if j >= 0:
                p = pos1[nums2[j]]
                dp2[j] = nums2[j] + max(dp2[j + 1], dp1[p + 1])
                j -= 1
        
        res = max(dp1[0], dp2[0])
        return res % (10 ** 9 + 7)


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        ret = s1 = s2 = 0
        n1, n2 = len(nums1), len(nums2)
        i = j = 0
        while i < n1 or j < n2 :
            if i == n1 :
                s2 += nums2[j]
                j += 1
            elif j == n2 :
                s1 += nums1[i]
                i += 1
            else :
                if nums1[i] < nums2[j] :
                    s1 += nums1[i]
                    i += 1
                elif nums1[i] > nums2[j] :
                    s2 += nums2[j]
                    j += 1
                else :
                    ret += max(s1, s2) + nums1[i]
                    s1 = s2 = 0
                    i += 1
                    j += 1
        
        ret += max(s1, s2)
        return ret % 1000000007

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        lens1, lens2 = len(nums1), len(nums2)
        dp1 = [0 for _ in range(lens1 + 1)]     
        dp2 = [0 for _ in range(lens2 + 1)]
        i, j = 1, 1
        while i < lens1 + 1 and j < lens2 + 1:
            if nums1[i-1] == nums2[j-1]:
                dp1[i] = max(dp1[i-1], dp2[j-1]) + nums1[i-1]
                dp2[j] = max(dp1[i-1], dp2[j-1]) + nums2[j-1]
                i += 1
                j += 1
            elif nums1[i-1] < nums2[j-1]:
                dp1[i] = dp1[i-1] + nums1[i-1]
                i += 1
            else:
                dp2[j] = dp2[j-1] + nums2[j-1]
                j += 1
        while i < lens1 + 1:
            dp1[i] = dp1[i-1] + nums1[i-1]
            i += 1
        while j < lens2 + 1:
            dp2[j] = dp2[j-1] + nums2[j-1]
            j += 1

        return max(dp1[-1], dp2[-1]) % (10**9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        len1=len(nums1)
        len2=len(nums2)
        dp1=[0 for i in range(len1+1)]
        dp2=[0 for i in range(len2+1)]
        i,j=1,1
        while(i<len1+1 and j<len2+1):
            if nums1[i-1]==nums2[j-1]:
                dp1[i]=nums1[i-1]+max(dp1[i-1],dp2[j-1])
                dp2[j]=nums2[j-1]+max(dp1[i-1],dp2[j-1])
                i+=1
                j+=1
            elif nums1[i-1]<nums2[j-1]:
                dp1[i]=nums1[i-1]+dp1[i-1]
                i+=1
            else:
                dp2[j]=nums2[j-1]+dp2[j-1]
                j+=1
        while(i<len1+1):
            dp1[i]=nums1[i-1]+dp1[i-1]
            i+=1
        while(j<len2+1):
            dp2[j]=nums2[j-1]+dp2[j-1]
            j+=1
        return max(dp1[-1],dp2[-1])%(10**9+7)


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        def getSum(i, nums1, j, nums2):
            total = 0
            while (i < len(nums1)):
                total += nums1[i]
                i += 1
                while (i < len(nums1) and j < len(nums2) and nums2[j] < nums1[i]):
                    j += 1

                if i < len(nums1) and j < len(nums2) and nums1[i] == nums2[j]:
                    if nums1[i] not in dp:
                        dp[nums1[i]] = max(getSum(i, nums1, j, nums2), getSum(j, nums2, i, nums1))
                    return total + dp[nums1[i]] 

            return total

        dp = {}
        return max(getSum(0, nums1, 0, nums2), getSum(0, nums2, 0, nums1)) % (10**9 + 7)


MOD = 1000000007
class Solution:
    def maxSum(self, nums1, nums2):
        sum1, sum2, res = 0, 0, 0
        p1, p2 = 0, 0
        while p1 <= len(nums1) - 1 or p2 <= len(nums2) - 1:
            if p1 <= len(nums1) - 1 and p2 <= len(nums2) - 1 and nums1[p1] == nums2[p2]:
                res = (res + max(sum1, sum2) + nums1[p1]) % MOD
                sum1, sum2 = 0, 0
                p1 += 1
                p2 += 1
            elif p2 > len(nums2) - 1 or (p1 <= len(nums1) - 1 and nums1[p1] < nums2[p2]):
                sum1 = sum1 + nums1[p1]
                p1 += 1
            else:
                sum2 = sum2 + nums2[p2]
                p2 += 1

        return (res + max(sum1, sum2)) % MOD

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        
        
        d1 = {}
        d2 = {}
        
        t1 = {}
        t2 = {}
        
        l1 = len(nums1)
        l2 = len(nums2)
        
        
        for i in range(l1):
            d1[nums1[i]] = i
            
        for i in range(l2):
            d2[nums2[i]] = i
            
            
        def runList1(i):
            
            if i == l1:
                return 0           
            
            if i in t1:
                return t1[i]
            
            maxList2 = 0
                        
            if i + 1 < l1 and  nums1[i+1] in d2:
                maxList2 = runList2(d2[nums1[i+1]])
                
            result = max(runList1(i+1), maxList2) + nums1[i]
            t1[i] = result
            return result
        
        
        def runList2(i):
            if i == l2:
                return 0
            
            if i in t2:
                return t2[i]
            
            maxList1 = 0
                       
            
            if i+1 < l2 and nums2[i+1] in d1:
                maxList1 = runList1(d1[nums2[i+1]])
                            
            result = max(runList2(i+1), maxList1) + nums2[i]
            
            t2[i] = result
            
            
            return result
             
        value = max(runList1(0), runList2(0)) 
        
        return value % (10**9 + 7)
        
        


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        sum1 = 0
        sum2 = 0
        s1 = 0
        s2 = 0
        total = 0
        # [2 4 5 8 10]
        # [4 6 8 9]
        l1 = len(nums1)
        l2 = len(nums2)
        while s1 < l1 and s2 < l2:
            if nums1[s1] < nums2[s2]:
                sum1 += nums1[s1]
                s1 += 1
            elif nums1[s1] > nums2[s2]:
                sum2 += nums2[s2]
                s2 += 1
            else:
                total += max(sum1, sum2) + nums1[s1]
                sum1 = sum2 = 0
                s1 += 1
                s2 += 1
        if s1 < l1:
            while s1 < l1:
                sum1 += nums1[s1]
                s1 += 1
            total += max(sum1, sum2)
        if s2 < l2:
            while s2 < l2:
                sum2 += nums2[s2]
                s2 += 1
            total += max(sum1, sum2)
        return total % ((10 ** 9) + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        n1,n2 = nums1,nums2
        s,t,sum1,sum2 = len(n1)-1,len(n2)-1,0,0
        ans = 0
        while s >= 0 and t >= 0:
            if n1[s] > n2[t]:
                sum1 += n1[s]
                s -= 1
            elif n1[s] < n2[t]:
                sum2 += n2[t]
                t -= 1
            else:
                ans += max(sum1+n1[s],sum2+n1[s])
                sum1 = sum2 = 0
                s -= 1
                t -= 1
        if s >= 0: ans += max(sum1+sum(n1[:s+1]),sum2)
        if t >= 0: ans += max(sum1,sum2+sum(n2[:t+1]))
        return ans % (10**9+7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        a, b = nums1, nums2
        m, n = len(a), len(b)
        p1 = {x:i for i, x in enumerate(a)}
        p2 = {x:i for i, x in enumerate(b)}
        
        @lru_cache(None)
        def dp(i, use_a):
            if use_a:
                if i == m:
                    return 0
                ans = a[i] + dp(i + 1, True)
                if a[i] in p2:
                    j = p2[a[i]] + 1
                    ans = max(ans, a[i] + dp(j, False))
            else:
                if i == n:
                    return 0
                ans = b[i] + dp(i +1, False)
                if b[i] in p1:
                    j = p1[b[i]] + 1
                    ans = max(ans, b[i] + dp(j, True))
            return ans 
        
        return max(dp(0, True), dp(0, False)) % (10 ** 9 + 7)
                


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        n1 = len(nums1)
        n2 = len(nums2)
        M = 1000000007
        dp1 = [0] * (n1+1)
        dp2 = [0] * (n2+1)
        i1 = i2 = 0
        while i1 < n1 and i2 < n2:
            if nums1[i1] < nums2[i2]:
                dp1[i1+1] = dp1[i1] + nums1[i1]
                i1 += 1
            elif nums1[i1] > nums2[i2]:
                dp2[i2+1] = dp2[i2] + nums2[i2]
                i2 += 1
            else:
                dp1[i1+1] = dp2[i2+1] = max(dp1[i1] + nums1[i1], dp2[i2] + nums2[i2])
                i1 += 1
                i2 += 1
        while i1 < n1:
            dp1[i1+1] = dp1[i1] + nums1[i1]
            i1 += 1
        while i2 < n2:
            dp2[i2+1] = dp2[i2] + nums2[i2]
            i2 += 1
        return max(dp1[n1], dp2[n2]) % M


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        memo1 = defaultdict(lambda: 0)
        memo2 = defaultdict(lambda: 0)
        nums1.append(0)
        nums2.append(0)
        
        i = len(nums1) - 2
        j = len(nums2) - 2
        while i >= 0 or j >= 0:
            n1 = nums1[i] if i >= 0 else 0
            n2 = nums2[j] if j >= 0 else 0
            
            if n1 == n2:
                memo1[n1] = max(n1 + memo1[nums1[i+1]], n2 + memo2[nums2[j+1]])
                memo2[n2] = memo1[n1]
                i -= 1
                j -= 1
            elif n1 > n2:
                memo1[n1] = max(n1 + memo1[nums1[i+1]], memo2[n1])
                i -= 1
            else:
                memo2[n2] = max(n2 + memo2[nums2[j+1]], memo1[n2])
                j -= 1
        
        return max(memo1[nums1[0]], memo2[nums2[0]]) % int(1e9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        l1 = len(nums1)
        l2 = len(nums2)
        index1 = 0
        index2 = 0
        score1 = 0
        score2 = 0
        maxScore = 0
        while index1 < l1 and  index2 < l2:
            n1 = nums1[index1]
            n2 = nums2[index2]
            if n1 == n2:
                score1 += n1
                score2 += n2
                if score1 < score2:
                    maxScore += score2
                else:
                    maxScore += score1
                score1 = 0
                score2 = 0
                index1 += 1
                index2 += 1
            elif n1 < n2:
                 score1 += n1
                 index1 += 1
            else:
                score2 += n2
                index2 += 1
        for i in range(index1,l1):
            score1 += nums1[i]
        for i in range(index2,l2):
            score2 += nums2[i]

        if score1 < score2:
            maxScore += score2
        else:
            maxScore += score1

        return maxScore%(10**9+7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        n1 = len(nums1)
        n2 = len(nums2)
        
        a1 = [-1 for _ in range(n1)]
        a2 = [-1 for _ in range(n2)]
        
        i, j = 0, 0
        while i < n1 and j < n2:
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                a1[i] = j
                a2[j] = i
                i += 1
                j += 1
        
        cache1 = {}
        cache2 = {}
        
        def process1(idx):
            if idx == n1:
                return 0
            if not idx in cache1:
                ans = 0
                if a1[idx] == -1:
                    ans = nums1[idx] + process1(idx+1)
                else:
                    ans = nums1[idx] + max(process1(idx+1), process2(a1[idx]+1))
                cache1[idx] = ans
            return cache1[idx]
        
        def process2(idx):
            if idx == n2:
                return 0
            if not idx in cache2:
                ans = 0
                if a2[idx] == -1:
                    ans = nums2[idx] + process2(idx+1)
                else:
                    ans = nums2[idx] + max(process2(idx+1), process1(a2[idx]+1))
                cache2[idx] = ans
            return cache2[idx]

        return max(process1(0), process2(0)) % (10 ** 9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        # [idxnums1,idxnums2,value]
        changeSum = 0
        partialSums = [[0,0]]
        i,j,k=0,0,0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                changeSum = (changeSum + nums1[i]) % (10**9 + 7)
                i += 1
                j += 1
                partialSums.append([0,0])
            elif nums1[i] < nums2[j]:
                partialSums[-1][0] += nums1[i]
                i += 1
            else:
                partialSums[-1][1] += nums2[j]
                j += 1
        while i < len(nums1):
            partialSums[-1][0] += nums1[i]
            i += 1
        while j < len(nums2):
            partialSums[-1][1] += nums2[j]
            j += 1
            
        print(changeSum)
        print(partialSums)
        for i in partialSums:
            changeSum += max(i)
        return changeSum % (10**9 + 7)
                


'''
https://leetcode.com/problems/get-the-maximum-score/


aproach 1: recursion brute force
  max(i+1, arr2[]) time O(n^n) space O(1)
 
approach 2: dp time O(n) space(n)


'''
class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
      # dictonary 1 {val : index}
        dict1 = {}
        dict2 = {}

        for i in range(len(nums1)):
            dict1[nums1[i]] = i

        # dictonary 2 {val : index}
        for i in range(len(nums2)):
            dict2[nums2[i]] = i

        dp1 = [0 for _ in nums1]
        dp2 = [0 for _ in nums2]
      
        def sol(index, curr):
            if curr == 1:
                if index == len(nums1):
                    return 0
                if not dp1[index]:
                    if nums1[index] in dict2:
                        indx2 = dict2[nums1[index]]
                        dp1[index] = max(sol(index+1, curr), sol(indx2+1, 2))  + nums1[index]
                    else:
                        dp1[index] = sol(index+1, curr)  + nums1[index]


                return dp1[index] 
        
            else:
                if index == len(nums2):
                    return 0
                if not dp2[index]:
                    if nums2[index] in dict1:
                        indx2 = dict1[nums2[index]]
                        dp2[index] = max(sol(index+1, curr), sol(indx2+1, 1)) + nums2[index]
                    else:
                        dp2[index] = sol(index+1, curr) + nums2[index]

                return dp2[index]
        
        sol(0,1)

        
        sol(0,2)
        

        return max(dp1[0], dp2[0]) % (10**9 + 7)



class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        if len(nums1)==0 or len(nums2)==0:
            return sum(nums2)+sum(nums1)
        
        n1,n2 = nums1,nums2
        s,t,sum1,sum2 = len(n1)-1,len(n2)-1,0,0
        ans = 0
        while s >= 0 and t >= 0:
            if n1[s] > n2[t]:
                sum1 += n1[s]
                s -= 1
            elif n1[s] < n2[t]:
                sum2 += n2[t]
                t -= 1
            else:
                ans += max(sum1+n1[s],sum2+n1[s])
                sum1 = sum2 = 0
                s -= 1
                t -= 1
        if s >= 0: ans += max(sum1+sum(n1[:s+1]),sum2)
        if t >= 0: ans += max(sum1,sum2+sum(n2[:t+1]))
        return ans % (10**9+7)

class Solution:
    def maxSum(self, arra: List[int], arrb: List[int]) -> int:
        m, n = len(arra), len(arrb)
        dica = {a: i for i, a in enumerate(arra)}
        dicb = {b: i for i, b in enumerate(arrb)}
        dpa, dpb = {}, {}
        
        def go(i, f):
            arr1, arr2 = arra, arrb
            dic1, dic2 = dica, dicb
            dp1, dp2 = dpa, dpb
            if not f:
                arr1, arr2 = arr2, arr1
                dic1, dic2 = dic2, dic1
                dp1, dp2 = dp2, dp1
            a = arr1[i]
            d = a + (dp1[arr1[i-1]] if i > 0 else 0)
            if a in dic2 and dic2[a] > 0:
                d = max(d, a+dp2[arr2[dic2[a]-1]])
            dp1[a] = d
        
        i, j = 0, 0
        while i < m and j < n:
            if arra[i] <= arrb[j]:
                go(i, True)
                i += 1
            else:
                go(j, False)
                j += 1
        
        while i < m:
            go(i, True)
            i += 1
        while j < n:
            go(j, False)
            j += 1
        return max(dpa[arra[-1]], dpb[arrb[-1]]) % (1000000007)


# 1537. Get the Maximum Score

from math import inf

def mix (A, B):
    ans = []
    i, j = 0, 0
    while i < len (A) or j < len (B):
        if i == len (A):   choice = 2
        elif j == len (B): choice = 1
        elif A[i] < B[j]:  choice = 1
        elif A[i] > B[j]:  choice = 2
        else:              choice = 3

        if choice == 1:
            ans.append ((A[i], choice))
            i += 1
        elif choice == 2:
            ans.append ((B[j], choice))
            j += 1
        elif choice == 3:
            ans.append ((A[i], choice))
            i, j = i+1, j+1
    return ans

def find_max (C, init):
    max0, max1 = -inf, -inf
    for i, (val, branches) in enumerate (C):
        if val == init:
            if branches == 1:
                new0, new1 = val, -inf
            elif branches == 2:
                new0, new1 = -inf, val
            else:
                new0, new1 = val, val
        else:
            if branches == 1:
                new0, new1 = max0 + val, max1
            elif branches == 2:
                new0, new1 = max0, max1 + val
            elif branches == 3:
                new0, new1 = max (max0, max1) + val, max (max0, max1) + val
        max0, max1 = new0, new1
    return max (max0, max1)

def find_max_score (A, B):
    C = mix (A, B)
    return max (find_max (C, A[0]), find_max (C, B[0]))

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        return find_max_score(nums1, nums2) % (10**9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        M, N = len(nums1), len(nums2)
        sum1, sum2 = 0, 0
        i, j = 0, 0
        res = 0
        while i < M and j < N:
            if nums1[i] < nums2[j]:
                sum1 += nums1[i]
                i += 1
            elif nums1[i] > nums2[j]:
                sum2 += nums2[j]
                j += 1
            else:
                res += max(sum1, sum2) + nums1[i]
                i += 1
                j += 1
                sum1 = 0
                sum2 = 0
                
        while i < M:
            sum1 += nums1[i]
            i += 1
        while j < N:
            sum2 += nums2[j]
            j += 1
        return (res + max(sum1, sum2)) % 1000000007


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        matrix = []
        matrix.append(nums1[:])
        matrix.append(nums2[:])
        dics = []
        dics.append({num: i for i, num in enumerate(nums1)})
        dics.append({num: i for i, num in enumerate(nums2)})
        sys.setrecursionlimit(10**6) 
        @lru_cache(None)
        def dfs(row, index):
            if index >= len(matrix[row]):
                return 0
            cur = matrix[row][index]
            res = cur + dfs(row, index+1)
            if cur in dics[1-row]:
                res = max(res, cur + dfs(1-row, dics[1-row][cur] + 1))
            return res
        mod = 10 ** 9 + 7
        return max(dfs(0, 0), dfs(1, 0)) % mod

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        
        
        
        @lru_cache(None)    
        def dp(idx1, idx2, top: bool):
            # print(idx1, idx2, top)
            
            if top:
                if idx1 < len(nums1):
                    while idx2 < len(nums2) and nums2[idx2] < nums1[idx1]:
                        idx2 += 1
                    if idx2 >= len(nums2):
                        return sum(nums1[idx1:])
                    if nums1[idx1] == nums2[idx2]:
                        return nums1[idx1] + max(dp(idx1+1, idx2+1, True), dp(idx1+1, idx2+1, False))
                    else:
                        return nums1[idx1] + dp(idx1+1, idx2, True)
                else:
                    return sum(nums1[idx1:])
            else:
                if idx2 < len(nums2):
                    while idx1 < len(nums1) and nums1[idx1] < nums2[idx2]:
                        idx1 += 1
                    if idx1 >= len(nums1):
                        return sum(nums2[idx2:])
                    if nums1[idx1] == nums2[idx2]:
                        return nums2[idx2] + max(dp(idx1+1, idx2+1, True), dp(idx1+1, idx2+1, False))
                    else:
                        return nums2[idx2] + dp(idx1, idx2+1, False)
                else:
                    return sum(nums2[idx2:])
                
        # for i in range(len(nums1)):
        #     for j in range(len(nums2)):
        #         for top in [True, False]:
        #             print(i,j,top, dp(i,j,top))
                    
        return max(dp(0,0,True), dp(0,0,False)) % (10**9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        rev1 = {v:k for k, v in enumerate(nums1)}
        rev2 = {v:k for k, v in enumerate(nums2)}
        
        def dp(val, memo):
            if val in memo:
                return memo[val]
            ans = 0
            if val in rev1:
                ans = val
                if rev1[val] < len(nums1) -1:
                    ans = max(ans, dp(nums1[rev1[val] + 1], memo) + val)
            if val in rev2:
                ans = max(ans, val)
                if rev2[val] < len(nums2) -1:
                    ans = max(ans, dp(nums2[rev2[val] + 1], memo) + val)
            ans = ans
            memo[val] = ans
            return ans
        memo = {}
        return max(dp(nums1[0], memo), dp(nums2[0], memo)) %(1000000007)

class Solution:
            
    
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        
        def f(i , p) :
            
            if ( p == 0 and i >= len(nums1) ) or ( p == 1 and i >= len(nums2) ) :
                return 0
            
            if (i , p) in dp :
                return dp[i , p]
            
            ans = f(i + 1 , p)
            
            if p == 0 :
                if  nums1[i] in b :
                    ans = max(ans , f(b[nums1[i]] + 1 , 1-p))
            
            else :
                if nums2[i] in a :
                    ans = max(ans , f(a[nums2[i]] + 1 , 1-p))
                
            dp[i , p] = ans + ( nums1[i] if p == 0 else nums2[i] )
            
            return dp[i,p]
        
        a , b , dp = {} , {} , {}
        for i , j in enumerate(nums1) :
            a[j] = i
            
        for i , j in enumerate(nums2) :
            b[j] = i
            
        return max(f(0 , 0) , f(0 , 1))%(10**9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        
        @lru_cache(None)    
        def dp(idx1, idx2, top: bool):
            
            if top:
                if idx1 < len(nums1):
                    while idx2 < len(nums2) and nums2[idx2] < nums1[idx1]:
                        idx2 += 1
                    if idx2 >= len(nums2):
                        return sum(nums1[idx1:])
                    if nums1[idx1] == nums2[idx2]:
                        return nums1[idx1] + max(dp(idx1+1, idx2+1, True), dp(idx1+1, idx2+1, False))
                    else:
                        return nums1[idx1] + dp(idx1+1, idx2, True)
                else:
                    return sum(nums1[idx1:])
            else:
                if idx2 < len(nums2):
                    while idx1 < len(nums1) and nums1[idx1] < nums2[idx2]:
                        idx1 += 1
                    if idx1 >= len(nums1):
                        return sum(nums2[idx2:])
                    if nums1[idx1] == nums2[idx2]:
                        return nums2[idx2] + max(dp(idx1+1, idx2+1, True), dp(idx1+1, idx2+1, False))
                    else:
                        return nums2[idx2] + dp(idx1, idx2+1, False)
                else:
                    return sum(nums2[idx2:])
                    
        return max(dp(0,0,True), dp(0,0,False)) % (10**9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        KMAX = 10 ** 9 + 7
        i1, i2 = 0, 0
        N1, N2 = len(nums1), len(nums2)
        res = 0
        total1, total2 = 0, 0
        while i1 < N1 or i2 < N2:
            if i1 == N1:
                total2 += nums2[i2]
                i2 += 1
                continue
            if i2 == N2:
                total1 += nums1[i1]
                i1 += 1
                continue
            if nums1[i1] == nums2[i2]:
                res += nums1[i1] + max(total1, total2)
                i1 += 1
                i2 += 1
                total1, total2 = 0, 0
            elif nums1[i1] < nums2[i2]:
                total1 += nums1[i1]
                i1 += 1
            else:
                total2 += nums2[i2]
                i2 += 1
        res += max(total1, total2)
        return res % KMAX        

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        M,N = len(nums1),len(nums2)
        i = 0
        j = 0
        sum1,sum2,res = 0,0,0
        while i < M and j < N:
            if nums1[i] < nums2[j]:
                sum1 += nums1[i]
                i += 1
            elif nums1[i] > nums2[j]:
                sum2 += nums2[j]
                j += 1
            else:
                res += max(sum1,sum2) + nums1[i]
                i += 1
                j += 1
                sum1 = sum2 = 0
                
        while i < M:
            sum1 += nums1[i]
            i += 1
        while j < N:
            sum2 += nums2[j]
            j += 1
        return (res + max(sum1,sum2)) % (10 ** 9 + 7)


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        dp1=[0 for i in range(len(nums1)+1)]
        dp2=[0 for i in range(len(nums2)+1)]
        i=1
        j=1
        while i<len(nums1)+1 and j<len(nums2)+1:
            if nums1[i-1]==nums2[j-1]:
                dp1[i]=max(dp1[i-1],dp2[j-1])+nums1[i-1]
                dp2[j]=max(dp1[i-1],dp2[j-1])+nums2[j-1]
                i+=1
                j+=1
                
            elif nums1[i-1]<nums2[j-1]:
                dp1[i]=dp1[i-1]+nums1[i-1]
                i+=1
            else:
                dp2[j]=dp2[j-1]+nums2[j-1]
                j+=1
        while i<len(nums1)+1:
            dp1[i]=dp1[i-1]+nums1[i-1]
            i+=1
            
        while j<len(nums2)+1:
            dp2[j]=dp2[j-1]+nums2[j-1]
            j+=1
        return max(dp1[-1],dp2[-1]) % (10**9+7)        

class Solution:
    def maxSum(self, x: List[int], y: List[int]) -> int:
        def f(i,p):
            if (p==0 and i>=len(x)) or (p==1 and i>=len(y)):return 0
            if (i,p) in dp:return dp[i,p]
            ans=f(i+1,p)
            if p==0:
                if x[i] in b :ans=max(f(b[x[i]]+1,1-p),ans)
            else:
                if y[i] in a:ans=max(f(a[y[i]]+1,1-p),ans)
            dp[i,p]=ans+(x[i] if p==0 else y[i])
            return dp[i,p]
        a,b,dp={},{},{}
        for j,i in enumerate(x):a[i]=j
        for j,i in enumerate(y):b[i]=j
        return max(f(0,0),f(0,1))%(10**9+7)

class Solution:
    def maxSum(self, A: List[int], B: List[int]) -> int:
        
        g = collections.defaultdict(list)
        
        for i in range(len(A)-1):
            g[A[i]].append(A[i+1])  
        for i in range(len(B)-1):
            g[B[i]].append(B[i+1])
        
        g[A[-1]]
        g[B[-1]]

        dp = collections.defaultdict(int)
        
        for node in sorted(g, reverse=True):
            
            dp[node] = node
            if g[node]:
                dp[node] += max(dp[nei] for nei in g[node])
            
        return max(dp.values()) % (10**9 + 7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        self.num1_idx = {x: i for i, x in enumerate(nums1)}
        self.num2_idx = {x: i for i, x in enumerate(nums2)}
        self.memo = {}
        s1 = self.helper(nums1, nums2, nums1[0])
        s2 = self.helper(nums1, nums2, nums2[0])
        return max(s1, s2) % (10**9 + 7)
    
    def helper(self, nums1, nums2, val):
        if val in self.memo:
            return self.memo[val]
        
        ans1, ans2 = 0, 0
        if val in self.num1_idx:
            idx = self.num1_idx[val]
            if idx + 1 < len(nums1):
                ans1 = self.helper(nums1, nums2, nums1[idx + 1])
        
        
        if val in self.num2_idx:
            idx = self.num2_idx[val]
            if idx + 1 < len(nums2):
                ans2 = self.helper(nums1, nums2, nums2[idx + 1])
        
        res = max(ans1, ans2) + val
        self.memo[val] = res
        return res
    


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        MOD = 1000000007
        Dict1 = defaultdict(int)
        Dict2 = defaultdict(int)
        for i in range(len(nums1)):
            Dict1[nums1[i]] = i+1 
        for i in range(len(nums2)):
            Dict2[nums2[i]] = i+1
        Dict3 = {}
        Dict4 = {}
        n1 = len(nums1)
        n2 = len(nums2)
        for i in nums1:
            if Dict1[i] >0 and Dict2[i] > 0:
                Dict3[i] = Dict2[i]
                Dict4[i] = Dict1[i]
        @lru_cache(None)
        def go(i , pos):
            if pos == 0:
                if i >= n1:
                    return 0
                ans = 0
                if Dict1[nums1[i]] >= 1 and Dict2[nums1[i]] >= 1:
                    ans = max(ans, go(i+1,pos)+nums1[i], go(Dict3[nums1[i]], (pos+1)%2)+nums1[i])
                else:
                    ans = max(ans, go(i+1, pos)+nums1[i])
                return ans
            else:
                if i >= n2:
                    return 0
                ans = 0
                if Dict1[nums2[i]] >= 1 and Dict2[nums2[i]] >= 1:
                    ans = max(ans, go(i+1,pos)+nums2[i], go(Dict4[nums2[i]],(pos+1)%2)+nums2[i])
                else:
                    ans = max(ans, go(i+1, pos)+nums2[i])
                return ans
        return max(go(0,0),go(0,1))%MOD


from collections import defaultdict
from functools import lru_cache
class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        mod = 10 ** 9 + 7
        mp = defaultdict(int) # key: (row_idx, elem_value), value: elem_index_in_row
        for i, x in enumerate(nums1):
            mp[(0, x)] = i
        for i, x in enumerate(nums2):
            mp[(1, x)] = i
        grid = [nums1, nums2]
        
        @lru_cache(None)
        def search(cur_row: int, i: int, prev_row: int) -> int:
            if cur_row == prev_row: # no row change
                res = (grid[cur_row][i] + (search(cur_row, i + 1, cur_row) if i + 1 < len(grid[cur_row]) else 0))
                if (1 - cur_row, grid[cur_row][i]) in mp:
                    j = mp[(1 - cur_row, grid[cur_row][i])]
                    res = max(res, search(1 - cur_row, j, cur_row))
                return res
            else: # changed row -> shouldn't change again
                return (grid[cur_row][i] + (search(cur_row, i + 1, cur_row) if i + 1 < len(grid[cur_row]) else 0))
        
        return max(search(0, 0, 0), search(1, 0, 1)) % mod

class Solution:
    def maxSum(self, a: List[int], b: List[int]) -> int:
        a2i = {n: i for i, n in enumerate(a)}
        b2i = {n: i for i, n in enumerate(b)}
        @lru_cache(None)
        def solve(i, is_a, switched):
            if is_a:
                c = a
                c2i = a2i
                d = b
                d2i = b2i
            else:
                c = b
                c2i = b2i
                d = a
                d2i = a2i
            add = 0 if switched else c[i]
            best = add
            if not switched and c[i] in d2i:
                best = add + solve(d2i[c[i]], not is_a, True)
            if i == len(c) - 1:
                return best
            return max(best, add + solve(i + 1, is_a, False))
        return max(solve(0, True, False), solve(0, False, False)) % (10**9 + 7)
            
            
            
        


import numpy

class Solution:

  def makeNewArray(self, num: List[int], breakpoint: List[int]):
    result = []
    flag = False
    bp_cur = 0
    sum = 0
    for index, value in enumerate(num):
      if bp_cur < len(breakpoint) and index == breakpoint[bp_cur]:
        if flag:
          result.append(sum)
        else:
          result.append(0)

        flag = False
        sum = 0
        result.append(value)
        bp_cur += 1
      else:
        sum += value
        flag = True

    if flag:
      result.append(sum)
    else:
      result.append(0)

    return result

  def maxSum(self, nums1: List[int], nums2: List[int]) -> int:

    result = 0
    cur0 = 0
    cur1 = 0
    bp0 = []
    bp1 = []
    while cur0 < len(nums1) and cur1 < len(nums2):
      if nums1[cur0] == nums2[cur1]:
        bp0.append(cur0)
        bp1.append(cur1)
        cur0 += 1
        cur1 += 1
      elif nums1[cur0] < nums2[cur1]:
        cur0 += 1
      else:
        cur1 += 1

    #print(\"[dbg] the breakpoint for arr0 is: \", bp0)
    new_arr0 = self.makeNewArray(nums1, bp0)
    #print(\"[dbg] the new array for arr1 is: \", new_arr0)

    #print(\"[dbg] the breakpoint for arr1 is: \", bp1)
    new_arr1 = self.makeNewArray(nums2, bp1)
    #print(\"[dbg] the new array for arr2 is: \", new_arr1)

    dim = (len(new_arr0), 2)
    dp = numpy.zeros(dim)

    dp[0][0] = new_arr0[0]
    dp[0][1] = new_arr1[0]

    #print(\"[dbg] the new len0:\", len(new_arr0))
    #print(\"[dbg] the new len1:\", len(new_arr1))

    for dx in range(1, len(new_arr1)):
      dp[dx][0] = max(dp[dx-1][0], dp[dx-1][1]) + new_arr0[dx]
      dp[dx][1] = max(dp[dx-1][0], dp[dx-1][1]) + new_arr1[dx]

    module = int(pow(10, 9) + 7)
    return int(max(dp[-1][0], dp[-1][1])) % module


from functools import lru_cache
class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        
        MOD = 10**9+7
        
        num_to_index1 = defaultdict(list)
        num_to_index2 = defaultdict(list)
        
        for i, num in enumerate(nums1):
            num_to_index1[num].append(i)
        for i, num in enumerate(nums2):
            num_to_index2[num].append(i)
            
        @lru_cache(None)
        def recurse (i, j):
            if i==1 and j == len(nums1)-1: return nums1[j]
            if i==2 and j == len(nums2)-1: return nums2[j]
            
            if i==1 : 
                option1 = nums1[j] + recurse (1, j+1)
                next_ind = num_to_index2.get(nums1[j+1], []) 
                if next_ind: 
                    next_ind = next_ind[0]
                    option2 = nums1[j] + recurse (2, next_ind)
                    return max(option1, option2)
                return option1
            
            if i==2: 
                option1 = nums2[j] + recurse (2, j+1)
                next_ind = num_to_index1.get(nums2[j+1], []) 
                if next_ind: 
                    next_ind = next_ind[0]
                    option2 = nums2[j] + recurse (1, next_ind)
                    return max(option1, option2)
                return option1
        
        return max(recurse (1, 0), recurse (2, 0)) % MOD

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        current_value = 0
        
        ptr1 = 0
        ptr2 = 0
        
        nums1Total = 0
        nums2Total = 0
        
        while ptr1 < len(nums1) and ptr2 < len(nums2):
            value1 = nums1[ptr1]
            value2 = nums2[ptr2]
            
            if value1 == value2:
                current_value += max(nums1Total, nums2Total) + value1
                ptr1 += 1
                ptr2 += 1
                nums1Total = 0
                nums2Total = 0
            elif value1 < value2:
                nums1Total += value1
                ptr1 += 1
            else:
                nums2Total += value2
                ptr2 += 1
            
        while ptr1 < len(nums1):
            nums1Total += nums1[ptr1]
            ptr1 += 1
        while ptr2 < len(nums2):
            nums2Total += nums2[ptr2]
            ptr2 += 1
        
        current_value += max(nums1Total, nums2Total)
            
        return current_value % (10 ** 9 + 7)


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        # graph = [[] for _ in range(10000007)]
        graph = {}
        u1, u2 = nums1[0], nums2[0]
        
        
        for n in range(len(nums1) - 1):
            u, v = nums1[n], nums1[n + 1]
            if u in graph:
                graph[u].append(v)
            else:
                graph[u] = [v]
        
        for n in range(len(nums2) - 1):
            u, v = nums2[n], nums2[n + 1]
            if u in graph:
                graph[u].append(v)
            else:
                graph[u] = [v]
        
        DP = {}
        MODN = 1000000007
        
        def solve(u):
            if u in DP:
                return DP[u]
            
            ans = u
            if u in graph:
                for v in graph[u]:
                    ans = max(ans, u + solve(v))
            DP[u] = ans
            return DP[u]
        
        
        ans = max(solve(u1), solve(u2)) % MODN
        return ans

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+100)
from collections import *

class Solution:
    def rec(self, t, i):
        if self.memo[t][i]!=-1:
            return self.memo[t][i]
    
        if i==0:
            return 0
        
        if t==0:
            res = self.rec(0, i-1)+self.nums1[i-1]
            
            if self.nums1[i-1] in self.idx2:
                res = max(res, self.rec(1, self.idx2[self.nums1[i-1]])+self.nums1[i-1])
        else:
            res = self.rec(1, i-1)+self.nums2[i-1]
            
            if self.nums2[i-1] in self.idx1:
                res = max(res, self.rec(0, self.idx1[self.nums2[i-1]])+self.nums2[i-1])
        
        self.memo[t][i] = res
        return res
    
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        m = len(nums2)
        self.nums1 = nums1
        self.nums2 = nums2
        self.idx1 = defaultdict(int)
        self.idx2 = defaultdict(int)
        
        for i in range(n):
            self.idx1[nums1[i]] = i
        
        for i in range(m):
            self.idx2[nums2[i]] = i
        
        self.memo = [[-1]*max(n+1, m+1) for _ in range(2)]
        return max(self.rec(0, n), self.rec(1, m))%(10**9+7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        common = set(nums1).intersection(set(nums2))
        
        segments1 = []
        tmp = 0
        for i in nums1:
            tmp+=i
            if i in common:
                segments1.append(tmp)
                tmp = 0
        segments1.append(tmp)    
            
        segments2 = []
        tmp = 0
        for i in nums2:
            tmp+=i
            if i in common:
                segments2.append(tmp)
                tmp = 0
        segments2.append(tmp)
        
        ans = 0
        for i in range(len(segments1)):
            ans+=max(segments1[i], segments2[i])
            
        return ans % (10**9+7)

'''
This seems to be dynamic programming where we have to find out the maximum score we can possibly get given the number of elements left to see in nums1 and nums2
'''
class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        BIG_INT = 10**9+7
        maxSums = {}
        num1Values = {}
        num2Values = {}
        num1Values[0] = -1
        for index, num in enumerate(nums1):
            num1Values[num] = index
        num2Values[0] = -1
        for index,num in enumerate(nums2):
            num2Values[num] = index
        num1Length = len(nums1)
        num2Length = len(nums2)
        nums1.append(0)
        nums2.append(0)
        def computeMaxSum(num1Left,num2Left):
            ##print(\"(num1Left,num2Left) is: \"+str((num1Left,num2Left)))
            if num1Left*num2Left == 0:
                return 0
            else:
                if (num1Left,num2Left) in maxSums:
                    return maxSums[(num1Left,num2Left)]
                current1 = 0 if num1Left == num1Length+1 else nums1[-num1Left-1]##had to do -num1Left-1 because we append 0 for future purposes of termination.
                current2 = 0 if num2Left == num2Length+1 else nums2[-num2Left-1]
                ##print(\"(current1,current2) is: \"+str((current1,current2)))
                if current1 == current2:
                    maxSums[(num1Left,num2Left)] = max(computeMaxSum(num1Left-1,num2Left)+nums1[-num1Left], computeMaxSum(num1Left,num2Left-1)+nums2[-num2Left])
                elif current1 > current2:
                    ##we can either progress to the next in current1 or possibly swap to current2.
                    if current1 in num2Values:
                        new2Index = num2Values[current1]
                        maxSums[(num1Left,num2Left)] = computeMaxSum(num1Left,num2Length-new2Index)##remember you do computeMaxSum before actually calling dictionary because you haven't set it in dictionary yet.
                    else:
                        maxSums[(num1Left,num2Left)] = computeMaxSum(num1Left-1,num2Left)+nums1[-num1Left]
                else:
                    ##we can either progress to the next in current2 or possibly swap to current1.
                    if current2 in num1Values:
                        new1Index = num1Values[current2]
                        maxSums[(num1Left,num2Left)] = computeMaxSum(num1Length-new1Index,num2Left)
                    else:
                        maxSums[(num1Left,num2Left)] = computeMaxSum(num1Left,num2Left-1)+nums2[-num2Left]
                return maxSums[(num1Left,num2Left)]
        return computeMaxSum(num1Length+1,num2Length+1)%BIG_INT


class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        accu1 = list(accumulate(nums1))
        accu2 = list(accumulate(nums2))
        #print(accu1)
        ans  = i = j = 0
        pi = pj = -1
        while i<len(nums1) and j<len(nums2):
            if nums1[i]<nums2[j]:
                i+=1
            elif nums1[i]>nums2[j]:
                j+=1
            else:
                ans+=max(accu1[i], accu2[j]) if pi<0 else max(accu1[i]-accu1[pi], accu2[j]-accu2[pj]) 
                pi,pj,i,j = i,j,i+1,j+1
        
        ans+=max(accu1[-1], accu2[-1]) if pi<0 else max(accu1[-1]-accu1[pi], accu2[-1]-accu2[pj]) 
        
        return ans % (10**9+7)

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        M, N = len(nums1), len(nums2)
        sum1, sum2 = 0, 0
        i, j = 0, 0
        res = 0
        while i < M and j < N:
            if nums1[i] < nums2[j]:
                sum1 += nums1[i]
                i += 1
            elif nums1[i] > nums2[j]:
                sum2 += nums2[j]
                j += 1
            else:
                res += max(sum1, sum2) + nums1[i]
                i += 1
                j += 1
                sum1 = 0
                sum2 = 0

        while i < M:
            sum1 += nums1[i]
            i += 1
        while j < N:
            sum2 += nums2[j]
            j += 1
        return (res + max(sum1, sum2)) % 1000000007