mice and cheese || java
Complexity

Time complexity:
O(nlogn)


Space complexity:
O(n)

Code
# Complexity
- Time complexity:
$$O(nlogn)$$

- Space complexity:
$$O(n)$$

# Code
```java []
class Solution {
    public int sum(int[] arr, int idx){
        int total = 0;
        for(int i = idx; i < arr.length; i++){
            total += arr[i];
        }
        return total;
    }

    // dp: TLE
    // public int helper(int[] arr1, int[] arr2, int k, int idx1, int idx2){
    //     if(k <= 0){
    //         return sum(arr2, idx2);
    //     }

    //     if(arr2.length - idx2 < k) return Integer.MIN_VALUE;

    //     if(idx1 >= arr1.length){
    //         return 0;
    //     }

    //     if(idx2 >= arr2.length){
    //         return 0;
    //     }

    //     return Math.max(arr1[idx1] + helper(arr1, arr2, k - 1, idx1 + 1, idx2 + 1), arr2[idx2] + helper(arr1, arr2, k, idx1 + 1, idx2 + 1));
    // }

    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        int total2 = sum(reward2, 0);
        if(k == 0) return total2;
        if(k == reward1.length) return sum(reward1, 0);

        int[] diff = new int[reward1.length];
        for(int i = 0; i < reward1.length; i++){
            diff[i] = reward2[i] - reward1[i];
        }

        Arrays.sort(diff);
        int idx = 0;
        while(k > 0){
            total2 -= diff[idx];
            idx++;
            k--;
        }

        return total2;
    }
}
```
['Java']