Get the Maximum Score

You are given two sorted arrays of distinct integers, arr1, and arr2. Your goal is to start from the beginning of one array, and arrive to the end of one array.

For each step, you can either move forward a step on an array, or move to somewhere the element in the target is the same as the element in your current square. Your total score is defined as the sum of all unique numbers that you have been on.

Find the maximum score that you can get given the above rules, modded by 10^9 + 7.

Parameters

  • arr1: A list of ordered, distinct integers.
  • arr2: Another list of ordered, distinct integers.

Result

  • The maximum score possible, modded by 10^9 + 7.

Examples

Example 1

Input: arr1 = [2, 4, 5, 8, 10], arr2 = [4, 6, 8, 9]

Output: 30

Explanation:

Constraints

  • 1 <= len(arr1), len(arr2) <= 50000
  • 1 <= arr1[i], arr2[i] <= 10^7
  • arr1[i] < arr1[j] for all i < j. Same goes for arr2.

Try it yourself

Solution

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

  >>> a = [1, 2, 3]
  >>> a[-1]
  3

Get premium for instant access to all content and solutions

Upgrade