Maximize Money in K Consecutive Bags

Maximize Money in K Consecutive Bags

You are given a list of bags, where each bag is represented as [position, amount]. You are also given an integer k, representing the maximum number of consecutive bags you can collect.

Two bags are considered 'consecutive' if their positions are adjacent in the sorted sequence of all bags (e.g., if you choose bag i, the next bag must be bag i+1). However, you can only collect a sequence of bags if the distance between the first and last bag in that sequence is no more than a given integer d.

Given the input bags (a list of pairs) and integers k and d, return the maximum total amount you can collect from any valid sequence of length at most k that spans a distance of no more than d.

Function Signature

def max_money(bags: List[List[int]], k: int, d: int) -> int:

Constraints

• 1 <= len(bags) <= 10^5
• 0 <= position <= 10^9
• 0 <= amount <= 10^4
• 1 <= k <= len(bags)
• 0 <= d <= 10^9

Examples

Example 1: Input: bags = [[1, 10], [2, 20], [5, 30], [6, 40]], k = 2, d = 2 Output: 70 Explanation:

• The sequence [5, 30] and [6, 40] has length 2 and distance 6-5=1 <= 2. Sum = 70.
• The sequence [1, 10] and [2, 20] has length 2 and distance 2-1=1 <= 2. Sum = 30.

Example 2: Input: bags = [[1, 5], [10, 5], [20, 5]], k = 2, d = 5 Output: 5 Explanation: No two bags are within distance 5 of each other, so the max is simply the largest single bag.