Bulk discount picks: hints, no solution

A wholesaler's price list has items, each with a promo code and a gain. When you take an item you earn its gain, but every item whose promo code is exactly one higher or exactly one lower than the code of the item you took is removed from the list. Items with the same code as a taken item stay available, and you may take as many of those as you like. Codes that differ by 2 or more do not interfere. Return the largest total gain you can earn. Taking nothing earns 0, and codes may repeat.

Examples

Input

codes = [3, 4, 3, 5, 7], gains = [6, 9, 4, 3, 8]

Output

21

Note

Take both items with code 3 (gain 10), the code 5 item (3) and the code 7 item (8).

Input

codes = [1, 2], gains = [5, 7]

Output

7

Note

Taking either item removes the other.

Input

codes = [10, 10, 10], gains = [2, 3, 4]

Output

9

Constraints

• 0 <= codes.length <= 2000, and gains has the same length
• 0 <= codes[i] <= 1000000000
• 1 <= gains[i] <= 10000

Hint 1: a nudge

If you take one item with some code, do you lose anything by also taking every other item with that same code? What does that let you say about each code as a whole?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing