'''
given you arr1 and arr2
you can do m operations
in each operation from front or back of arr2 pick an element and put it in front or back of arr1
by doing these m operations find out the max subarray sum possible


-------------------------------------------------------------------------------------

important thing to be noted here is

lets focus on how we can pick out m elements
place 2 pointers at start and end of arr2 and pick out m elements with m comparisions
once you have popped out m max elements from front or back of the arr2
you need to filter out positive elements from them and form a good sum
say in this way you got a good sum 20
now say you were given an array
5 -100 10
you have 2 choices as per question you can put all of those postive (good sum)
either at front or back ,you need to try to get the ans as 30 not settle for 25
so the answer would be max(max kadane with goodsum at front ,max kadane with goodsum at back)



'''

class Solution:

    def maxSubArraySumWithMops(self,arr1,arr2,m):
        #m will be always <= len(arr2)
        left = 0 
        right = len(arr2)-1
        maxArr2 = []
        goodSum = 0

        while m and left<=right:
            if arr2[left]>arr2[right]:
                maxArr2.append(arr2[left])
                left += 1
            else:
                maxArr2.append(arr2[right])
                right -= 1
            m-=1
            
        for ele in maxArr2:
            if ele>0:
                goodSum+=ele 
        
        temp1 = [ele for ele in arr1]
        temp2 = [ele for ele in arr1]
        temp1.insert(goodSum,0)
        temp2.append(goodSum)
        maxi = -10**10
        print(f"goodsum is {goodSum}")
        #finding kadane when goodsum placed at left
        prev = -10**10
        for ele in temp1:
            prev = max(prev+ele,ele,0)
            maxi = max(maxi,prev)
             

        #finding kadane when goodsum placed at right
        prev = -10**10
        for ele in temp2:
            prev = max(prev+ele,ele,0)
            maxi = max(maxi,prev)




        return maxi
        
       

if __name__ == "__main__":
    sol = Solution()

    # Each test case is (arr1, arr2, m)
    test_cases = [
        ([1,3,-5,2,2], [2,3], 2),
        ([5, -100, 10], [10,10,10], 2),                # example from description
        ([1, 2, 3], [4, 5, 6], 3),                       # all positive, pick all
        ([10, -5, 7], [-1, -2, -3], 2),                  # arr2 all negative
        ([1, 2, 3, 4], [5, 6, 7, 8], 1),                 # pick one from arr2
        ([0, 0, 0], [1, 2, 3], 2),                       # arr1 zeros
        ([1], [2], 1),                                   # single element each
        ([1, -2, 3], [4, -5, 6], 2),                     # mixed arr2
        ([1, 2, 3], [], 0),                              # arr2 empty, no ops
        ([1, 2, 3], [4, 5, 6], 0),                       # m=0, no ops
        ([1, 2, 3], [4, 5, 6], 10),                      # m > len(arr2)
    ]

    for idx, (arr1, arr2, m) in enumerate(test_cases, start=1):
        try:
            result = sol.maxSubArraySumWithMops(list(arr1), list(arr2), m)
        except Exception as e:
            result = f"Error: {e}"
        print(f"Test case {idx}: arr1={arr1} arr2={arr2} m={m} -> Result: {result}")