class Solution:
    def maxSumDivThree(self, nums):
        # dp[i] = max sum such that sum % 3 == i
        # Start with 0 at index 0, and float('-inf') for others
        dp = [0, float('-inf'), float('-inf')]
        
        for num in nums:
            # Use a temporary list to store updates for this current number
            # so we don't use the same number twice in one transition
            next_dp = dp[:]
            
            for current_sum in dp:
                if current_sum == float('-inf'):
                    continue
                    
                new_sum = current_sum + num
                remainder = new_sum % 3
                
                # Update the state if the new sum is larger than what we have
                if new_sum > next_dp[remainder]:
                    next_dp[remainder] = new_sum
            
            dp = next_dp
            
        return dp[0]

def maxSumDivThree_Greedy(nums):
    total_sum = sum(nums)
    remainder = total_sum % 3
    
    if remainder == 0:
        return total_sum
    
    # Store the two smallest numbers for remainder 1 and remainder 2
    # Initialized to infinity
    rem1 = sorted([n for n in nums if n % 3 == 1])[:2]
    rem2 = sorted([n for n in nums if n % 3 == 2])[:2]
    
    ans = 0
    if remainder == 1:
        # Option A: Remove the smallest rem1
        # Option B: Remove the two smallest rem2
        res1 = total_sum - rem1[0] if len(rem1) >= 1 else 0
        res2 = total_sum - sum(rem2) if len(rem2) >= 2 else 0
        ans = max(res1, res2)
        
    elif remainder == 2:
        # Option A: Remove the smallest rem2
        # Option B: Remove the two smallest rem1
        res1 = total_sum - rem2[0] if len(rem2) >= 1 else 0
        res2 = total_sum - sum(rem1) if len(rem1) >= 2 else 0
        ans = max(res1, res2)
        
    return ans