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: MEDIUM
Tags: Dynamic programming

Data structures

Amortized analysis

Greedy algorithms
Skill types: Dynamic programming

Amortized analysis

Data structures

Greedy algorithms

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:
		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])
		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)
		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))
		elif 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))
		self.f(nums1, nums2, 1, 0)
		self.f(nums1, nums2, 0, 0)
		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):
		if high >= low:
			mid = (high + low) // 2
			if arr[mid] == x:
				return mid
			elif arr[mid] > x:
				return self.binary_search(arr, low, mid - 1, x)
			else:
				return self.binary_search(arr, mid + 1, high, x)
		else:
			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)
			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
		maxSum = maxSum % modulo
		return maxSum


class Solution:

	def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
		(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) % 1000000007


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


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
			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
				sumMax += sumT
				sumMax = sumMax % maxVal
				idx2[v2] = i
				if v2 > nums1[-1]:
					break
		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:
		(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])
				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:
		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:
		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)
			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, 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:
		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:
		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)
		for i in range(n):
			if nums2[i] in st1:
				cm1.append(d[nums2[i]])
				cm2.append(i)
		ans = 0
		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
		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
		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
		while i >= 0:
			dp1[i] = nums1[i] + dp1[i + 1]
			i -= 1
		while j >= 0:
			dp2[j] = nums2[j] + dp2[j + 1]
			j -= 1
		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:
		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
		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

		def _dp(ii, its1, val):
			nums = nums1 if its1 else nums2
			oums = nums2 if its1 else nums1
			if ii == len(nums):
				return val
			if nums[ii] in oums:
				ix = oums.index(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.0

		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()))
		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
			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]
		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]
		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:
		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))
		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]))
			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:]))
		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
			elif 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:

		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)


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
		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:
		(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(1000000000.0 + 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:
		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)


class Solution:

	def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
		dict1 = {}
		dict2 = {}
		for i in range(len(nums1)):
			dict1[nums1[i]] = i
		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, 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


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)
		elif 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:
		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):
			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:])
			elif 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:
		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))
			elif 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:
		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, 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)
		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:
				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:
				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
		new_arr0 = self.makeNewArray(nums1, bp0)
		new_arr1 = self.makeNewArray(nums2, bp1)
		dim = (len(new_arr0), 2)
		dp = numpy.zeros(dim)
		dp[0][0] = new_arr0[0]
		dp[0][1] = new_arr1[0]
		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 = {}
		(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)


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):
			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]
				current2 = 0 if num2Left == num2Length + 1 else nums2[-num2Left - 1]
				if current1 == current2:
					maxSums[num1Left, num2Left] = max(computeMaxSum(num1Left - 1, num2Left) + nums1[-num1Left], computeMaxSum(num1Left, num2Left - 1) + nums2[-num2Left])
				elif current1 > current2:
					if current1 in num2Values:
						new2Index = num2Values[current1]
						maxSums[num1Left, num2Left] = computeMaxSum(num1Left, num2Length - new2Index)
					else:
						maxSums[num1Left, num2Left] = computeMaxSum(num1Left - 1, num2Left) + nums1[-num1Left]
				elif 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