Untitled

public class MaximumFruits {
    public int maxFruits(int[][] fruits, int startPos, int k) {
        int n = fruits.length;
        int maxPosition = fruits[n - 1][0];
        
        // Step 1: Construct prefix sum array
        int[] prefixSum = new int[maxPosition + 2];
        for (int[] fruit : fruits) {
            prefixSum[fruit[0] + 1] += fruit[1];
        }
        for (int i = 1; i <= maxPosition + 1; i++) {
            prefixSum[i] += prefixSum[i - 1];
        }
        
        int maxFruits = 0;
        
        // Step 2: Move left first, then right
        for (int leftSteps = 0; leftSteps <= Math.min(k, startPos); leftSteps++) {
            int leftPos = startPos - leftSteps;
            int rightSteps = k - 2 * leftSteps;
            int rightPos = Math.min(maxPosition, startPos + rightSteps);
            maxFruits = Math.max(maxFruits, prefixSum[rightPos + 1] - prefixSum[leftPos]);
        }
        
        // Step 3: Move right first, then left
        for (int rightSteps = 0; rightSteps <= k; rightSteps++) {
            int rightPos = startPos + rightSteps;
            if (rightPos > maxPosition) break;
            int leftSteps = k - 2 * rightSteps;
            int leftPos = Math.max(0, startPos - leftSteps);
            maxFruits = Math.max(maxFruits, prefixSum[rightPos + 1] - prefixSum[leftPos]);
        }
        
        return maxFruits;
    }

    public static void main(String[] args) {
        MaximumFruits solution = new MaximumFruits();
        System.out.println(solution.maxFruits(new int[][]{{2, 8}, {6, 3}, {8, 6}}, 5, 4)); // Output: 9
        System.out.println(solution.maxFruits(new int[][]{{0, 9}, {4, 1}, {5, 7}, {6, 2}, {7, 4}, {10, 9}}, 5, 4)); // Output: 14
        System.out.println(solution.maxFruits(new int[][]{{0, 3}, {6, 4}, {8, 5}}, 3, 2)); // Output: 0
    }
}