A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.
Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level  i.e.  time[i]*satisfaction[i]
Return the maximum sum of Like-time coefficient that the chef can obtain after dishes preparation.
Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.
 
Example 1:
Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total Like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14). Each dish is prepared in one unit of time.
Example 2:
Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)

Example 3:
Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People don't like the dishes. No dish is prepared.

Example 4:
Input: satisfaction = [-2,5,-1,0,3,-3]
Output: 35

 
Constraints:

n == satisfaction.length
1 <= n <= 500
-10^3 <= satisfaction[i] <= 10^3

Difficulty: interview

Starter code:

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        

Solutions:
class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        
        satisfaction.sort()
        total, res = 0,0
        
        while satisfaction and satisfaction[-1]+total > 0:
            total += satisfaction.pop()
            res += total
            
        return res


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        s = 0
        counter = 1
        for i in satisfaction:
            s += i*counter
            counter += 1
        check = s
        longest = s
        while True:
            s = 0
            counter = 1
            for i in satisfaction:
                s += i*counter
                counter += 1
            if s < check:
                return check
            if s > check:
                longest = s
            check = s
            if len(satisfaction) == 0:
                return longest
            del satisfaction[0]
            


class Solution:
    def maxSatisfaction(self, sat: List[int]) -> int:
        sat.sort()
        split = 0
        while split < len(sat) and sat[split] < 0:
            split += 1
        if split == len(sat): return 0
        cur_sum,i,unit = 0,1,0
        for x in sat[split:]:
            cur_sum += (i*x)
            unit += x
            i += 1
        self.max = cur_sum
        #print(split, cur_sum, unit)
        for i in range(split-1,-1,-1):
            r,diff,psum=1,0,cur_sum
            for j in range(i,split):
                diff += (r*sat[j])
                r += 1
                psum += unit
            psum += diff
            if psum > self.max:
                self.max = psum
        return self.max
                
                
        
        


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()

        positive_sum, positive_step, positive_count = 0, 0, 0
        for i in satisfaction:
            if i < 0:
                continue
            positive_count += 1
            positive_sum += positive_count*i
            positive_step += i

        negative_count = len(satisfaction) - positive_count
        result = [positive_sum]
        for i in range(negative_count):

            negative_sum = 0
            for j in range(i+1):
                negative_sum += satisfaction[negative_count-j-1]*(i-j+1)
            result.append(negative_sum + positive_sum + positive_step*(i+1))

        return max(result)

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        s=0
        res=0
        for a in satisfaction:
            s+=a
            if s<=0:
                break
            res+=s
        return res
    
    
    
    
    '''
    将所有大于的的前缀子串都加上
    大数尽可能多家几次，所以先倒序
    到当前位置的前缀和
    一直计算前缀和，直到前缀和<=0  结束
    [9, 8, 5, 2, 1, -1]
sum = 9 * 4 + 8 * 3 + 2 * 3 + 1 * 2 + -1 * 1
<=>
sum += 9
sum += (9 + 8 = 17)
sum += (17 + 2 = 19)
sum += (19 + 1 = 20)
sum += (20 – 1 = 19)
    '''

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        
        if satisfaction[0] >= 0:
            return calc_satisfaction(satisfaction)
        
        min_val = -sys.maxsize
        min_index = None
        for i,v in enumerate(satisfaction):
            if 0 > v > min_val:
                min_index = i
                min_val = v
        #curr_satisfaction = calc_satisfaction(satisfaction[min_index+1:])
        curr_sum = sum(satisfaction[min_index+1:])
        while min_index >= 0:
            print((min_index, satisfaction))
            print((satisfaction[min_index], curr_sum))
            if abs(satisfaction[min_index]) < curr_sum:
                curr_sum = curr_sum + satisfaction[min_index]
            else:
                break
            min_index -= 1
        
        print((min_index, satisfaction))
        return calc_satisfaction(satisfaction[min_index+1:])

    
def calc_satisfaction(dishes):
    total = 0
    for i,s in enumerate(dishes):
        total += (i+1) * s
    return total


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        best = 0
        total = 0
        for i in range(len(satisfaction)-1, -1, -1):
            for j in range(len(satisfaction)-1, i-1, -1):
                total += satisfaction[j]
            best = max(best, total)
        return best

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        s = 0
        counter = 1
        for i in satisfaction:
            s += i*counter
            counter += 1
        check = s
        longest = s
        while True:
            s = 0
            counter = 1
            for i in satisfaction:
                s += i*counter
                counter += 1
            if s < check:
                return check
            if s > check:
                longest = s
            check = s
            if len(satisfaction) == 0:
                return longest
            satisfaction = satisfaction[1:]
            


from numpy import dot

def coefficient(arr):
    if len(arr) <= 0:
        return 0
    return dot(arr,list(range(1,len(arr)+1)))
    # res = 0
    # for i in range(len(arr)):
    #     res += (i+1)*arr[i]
    # return res

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        runningSum = 0
        for i in reversed(list(range(len(satisfaction)))):
            runningSum += satisfaction[i]
            if runningSum <= 0:
                return coefficient(satisfaction[i+1:])
        return coefficient(satisfaction)


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        if max(satisfaction) <= 0:
            return 0
        
        
        satisfaction.sort()

        
        if satisfaction[0] > 0:
            output = 0
            for i, v in enumerate(satisfaction):
                output += (i+1) * v
            return output
        
        min_val = min(i for i in satisfaction if i >= 0) 
        min_index = satisfaction.index(min_val)
        
        temp_satisfaction = satisfaction[min_index:]
        
        prev = -1
        current_sum = 0
        while current_sum > prev and len(temp_satisfaction) <= len(satisfaction):
            prev = current_sum
            current_sum = 0
            for i, v in enumerate(temp_satisfaction):
                current_sum += (i+1) * v
                
            
            min_index -= 1
            temp_satisfaction.insert(0, satisfaction[min_index])
            

        return prev if prev > current_sum else current_sum
        


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        
        if satisfaction[0] >= 0:
            return calc_satisfaction(satisfaction)
        
        min_val = -sys.maxsize
        min_index = None
        for i,v in enumerate(satisfaction):
            if 0 > v > min_val:
                min_index = i
                min_val = v
                
        curr_satisfaction = calc_satisfaction(satisfaction[min_index+1:])
        while True:
            min_index -= 1
            temp_satisfaction = calc_satisfaction(satisfaction[min_index+1:])
            if temp_satisfaction > curr_satisfaction:
                curr_satisfaction = temp_satisfaction
            else:
                break
                
        return curr_satisfaction

    
def calc_satisfaction(dishes):
    total = 0
    for i,s in enumerate(dishes):
        total += (i+1) * s
    return total


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        
        if satisfaction[0] >= 0:
            return calc_satisfaction(satisfaction)
        
        min_val = max(s for s in satisfaction if s < 0)
        min_index = satisfaction.index(min_val)
        '''
        for s in satisfaction:
            if s >= 0:
                beneficial.append(s) # [0, 2, 5]
            else:
                negative.append(s)  # [-3, -2]
        '''
        curr_satisfaction = calc_satisfaction(satisfaction[min_index+1:])
        while True:
            min_index -= 1
            temp_satisfaction = calc_satisfaction(satisfaction[min_index+1:])
            if temp_satisfaction > curr_satisfaction:
                curr_satisfaction = temp_satisfaction
            else:
                break
                
        return curr_satisfaction

    
def calc_satisfaction(dishes):
    total = 0
    for i,s in enumerate(dishes):
        total += (i+1) * s
    return total


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        total = 0
        beneficial = deque()
        negative = []
        
        if satisfaction[0] > 0:
            return calc_satisfaction(satisfaction)
        
        for s in satisfaction:
            if s >= 0:
                beneficial.append(s) # [0, 2, 5]
            else:
                negative.append(s)  # [-3, -2]

        curr_satisfaction = calc_satisfaction(beneficial)
        for s in reversed(negative):
            beneficial.appendleft(s)
            temp_satisfaction = calc_satisfaction(beneficial)
            if temp_satisfaction > curr_satisfaction:
                curr_satisfaction = temp_satisfaction
            else:
                beneficial.popleft()
                break
                
        return curr_satisfaction

    
def calc_satisfaction(dishes):
    total = 0
    for i,s in enumerate(dishes):
        total += (i+1) * s
    return total


from collections import deque


class Solution:

  def ComputeLikeTime(self, prepared_dishes):
    like_time = 0
    dish_index = 1
    for satisfaction in prepared_dishes:
      like_time += (dish_index * satisfaction)
      dish_index += 1
    return like_time

  def maxSatisfaction(self, satisfaction):
    satisfaction = sorted(satisfaction, reverse=True)
    prepared_dishes = deque()
    max_satisfaction = 0
    for val in satisfaction:
      prepared_dishes.appendleft(val)
      satisfaction = self.ComputeLikeTime(prepared_dishes)
      if satisfaction > max_satisfaction:
        max_satisfaction = satisfaction
    return max_satisfaction

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        
        if satisfaction[0] >= 0:
            return calc_satisfaction(satisfaction)
        
        min_val = -sys.maxsize
        min_index = None
        print(satisfaction)
        for i,v in enumerate(satisfaction):
            if 0 > v > min_val:
                min_index = i
                min_val = v
        print((min_val, min_index))
                
        curr_satisfaction = calc_satisfaction(satisfaction[min_index+1:])
        while True:
            min_index -= 1
            temp_satisfaction = calc_satisfaction(satisfaction[min_index+1:])
            if temp_satisfaction > curr_satisfaction:
                curr_satisfaction = temp_satisfaction
            else:
                break
                
        return curr_satisfaction

    
def calc_satisfaction(dishes):
    total = 0
    for i,s in enumerate(dishes):
        total += (i+1) * s
    return total


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        total = 0
        beneficial = deque()
        negative = []
        def calc_satisfaction(dishes):
            total = 0
            for i,s in enumerate(dishes):
                total += (i+1) * s
            return total
        
        for s in satisfaction:
            if s >= 0:
                beneficial.append(s)
            else:
                negative.append(s)

        curr_satisfaction = calc_satisfaction(beneficial)
        for s in reversed(negative):
            temp_satisfaction = calc_satisfaction(deque([s]) + beneficial)
            if temp_satisfaction > curr_satisfaction:
                curr_satisfaction = temp_satisfaction
                beneficial.appendleft(s)
            else:
                break
                
        return curr_satisfaction

    



class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        sat_sort = sorted(satisfaction)
        max_sat = 0
        for i in range(len(sat_sort)):
            sat = sum(t*s for t, s in enumerate(sat_sort[i:],start=1))
            max_sat = max(max_sat,sat,0)
        return max_sat


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        sorted_satis = sorted(satisfaction)
        max_satis = sorted_satis[-1]
        
        if max_satis <= 0:
            return 0
            
        def calculate_satisfaction(start_index):
            s = 0
            for i in range(len(sorted_satis) - start_index):
                s += (i + 1) * sorted_satis[start_index + i]
            return s
            
            
        max_satisfaction = -1;
        
        for i in range(len(sorted_satis)):
            max_satisfaction = max(max_satisfaction, calculate_satisfaction(i))      
            if sorted_satis[i] >= 0:
                return max_satisfaction
        
        return max_satisfaction


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        best = 0
        for i in range(len(satisfaction)):
            count = 1
            val = 0
            for j in range(i, len(satisfaction)):
                val += satisfaction[j] * count
                count += 1
            best = max(best, val)
        return best

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        max_satisfaction = 0
        for i in range(0, len(satisfaction)):
            curr_satisfaction = 0
            timestamp = 1
            for j in range(i, len(satisfaction)):
                curr_satisfaction += satisfaction[j] * timestamp
                timestamp += 1
            max_satisfaction = max(max_satisfaction, curr_satisfaction)
        return max_satisfaction
            
#         cache = {}
#         def maxSatisfactionHelper(satisfaction, start, timestamp):
#             if not satisfaction:
#                 return 0
            
#             if (start,timestamp) in cache:
#                 return cache[(start, timestamp)]
            
#             max_satisfaction = 0
            
#             max_satisfaction = max((satisfaction[0] * timestamp) +                           maxSatisfactionHelper(satisfaction[1:], start+1, timestamp + 1), 
#                                   maxSatisfactionHelper(satisfaction[1:], start+1, timestamp))
            
#             cache[(start, timestamp)] = max_satisfaction
#             return max_satisfaction
        
#         return maxSatisfactionHelper(sorted(satisfaction), 0, 1)
            


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:

        satisfaction.sort(reverse=True)
        ans = cur_sum = 0
        for ele in satisfaction:
            cur_sum += ele
            if cur_sum >= 0:
                ans += cur_sum

        return ans; 

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        output = 0
        result = 0
        for i in range(len(satisfaction)):
            output += satisfaction[i]*i
        
        for i in range(0,len(satisfaction)):
            for j in range(i,len(satisfaction)):
                result += satisfaction[j]*(j-i+1)
            if output < result:
                output = result
            result = 0
        if output < 0 :
            output = 0
        return output

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        s = sorted(satisfaction, reverse=True)
        total = 0
        i = 0 
        while i < len(satisfaction): 
            total = max(sum([x*(i+1) for i,x in enumerate(s[0:i+1][::-1])]), total) 
            i+=1
        return total


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        dishes = len(satisfaction)
        best = 0
        for i in range(dishes):
            sum = 0
            tmp = satisfaction[-i-1:dishes]
            for j,val in enumerate(tmp):
                sum+=(j+1)*val
            best = max(best,sum)
        return best

class Solution:
    def mergeSort(self, lst: List[int]) -> int:
        n = len(lst)
        
        # base case
        if n <= 1:
            return lst
        
        mid = n // 2
        L   = lst[:mid]
        R   = lst[mid:]
        
        self.mergeSort(L)
        self.mergeSort(R)
        
        i, j, k = 0, 0, 0
        while (i < len(L)) and (j < len(R)):
            if (L[i] < R[j]):
                lst[k] = L[i]
                i += 1
                
            else:
                lst[k] = R[j]
                j += 1
                
            k += 1
        
        # fill remaining
        while (i < len(L)):
            lst[k] = L[i]
            i += 1
            k += 1
            
        while (j < len(R)):
            lst[k] = R[j]
            j += 1
            k += 1 
        
        return lst
    
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        n = len(satisfaction)
        possible_sums = [None for i in range(n)]
        print('.......')
        self.mergeSort(satisfaction)
        print(satisfaction)
        
        for i in range(n):
            arr = satisfaction[i:]
            like_times = [((j+1) * arr[j]) for j in range(len(arr))]
            possible_sums[i] = sum(like_times)
        
        return max(max(possible_sums), 0)
        
        


class Solution:
    def mergeSort(self, lst: List[int]) -> int:
        n = len(lst)
        
        # base case
        if n <= 1:
            return lst
        
        mid = n // 2
        L   = lst[:mid]
        R   = lst[mid:]
        
        self.mergeSort(L)
        self.mergeSort(R)
        
        i, j, k = 0, 0, 0
        while (i < len(L)) and (j < len(R)):
            if (L[i] < R[j]):
                lst[k] = L[i]
                i += 1
                
            else:
                lst[k] = R[j]
                j += 1
                
            k += 1
        
        # fill remaining
        while (i < len(L)):
            lst[k] = L[i]
            i += 1
            k += 1
            
        while (j < len(R)):
            lst[k] = R[j]
            j += 1
            k += 1 
        
        return lst
    
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        n = len(satisfaction)
        possible_sums = [None for i in range(n)]
        self.mergeSort(satisfaction)
        
        for i in range(n):
            arr = satisfaction[i:]
            like_times = [((j+1) * arr[j]) for j in range(len(arr))]
            possible_sums[i] = sum(like_times)
        
        return max(max(possible_sums), 0)
        
        


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        score = 0
        
        satisfaction.sort()
        print (satisfaction)
        if satisfaction[0] >= 0:
            for i in range(len(satisfaction)):
                score += (i+1) * satisfaction[i]
            return score
        elif satisfaction[len(satisfaction)-1] <= 0:
            return score
        else:
            for i in range(len(satisfaction)):
                score += (i+1) * satisfaction[i]
            
            badDishes = []
            for sat in satisfaction:
                if sat < 0:
                    badDishes.append(sat)
            #print(badDishes)
            for bad in badDishes:
                satisfaction.remove(bad)
                print(satisfaction)
                temp_best = 0
                for i in range(len(satisfaction)):
                    temp_best += (i+1) * satisfaction[i]
                print(temp_best)
                if temp_best > score:
                    score = temp_best
            return score

class Solution:

    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        temp = [0] * len(satisfaction)
        output = 0
        satisfaction.sort()
        for i, _ in enumerate(satisfaction):
            for j, s in enumerate(satisfaction[i:]): 
                temp[i] += s*(j+1)

        for s in temp: 
            if s > output: 
                output = s

        return output


class Solution:
    def maxSatisfaction(self, sat: List[int]) -> int:
        sat = sorted(sat)
        out = [0]
        while len(sat) > 0:
            value = 0
            for i, v in enumerate(sat):
                value += v*(i+1)
            out.append(value)
            print(sat)
            if sat[0]>0:
                break
            sat = sat[1:]
        return max(out)
            


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
#         table = [[None]*len(satisfaction) for i in range(len(satisfaction))]
#         for i in range(len(satisfaction)):
#             for j in range(i,len(satisfaction)):
#                 table[i][j] = satisfaction[j]*(i+1)
#         bestSat = float('-inf')
#         for i in range(len(satisfaction)):
#             row = i
#             col = len(satisfaction)-1
#             currSat = 0
#             while row >= 0:
#                 currSat += table[row][col]
#                 row -= 1
#                 col -= 1
#             bestSat = max(bestSat,currSat)
#         return max(bestSat,0)
    
        bestSat = float('-inf')
        for i in range(len(satisfaction)):
            n = len(satisfaction)-1
            numItems = i+1
            numAdded = 0
            currSat = 0
            while numAdded <= numItems:
                currSat += satisfaction[n-numAdded]*(numItems-numAdded)
                numAdded += 1
            bestSat = max(bestSat,currSat)
        return max(bestSat,0)

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        highScore = 0
        satisfaction.sort(reverse = True)
        
        for n in range(len(satisfaction)):
            sortedSatisfaction = satisfaction[:len(satisfaction)-n]
            sumSatisfaction = 0
            for i in range(len(sortedSatisfaction)):
                multiplier = len(sortedSatisfaction) - i
                sumSatisfaction += sortedSatisfaction[i] * multiplier
                
            if sumSatisfaction > highScore:
                highScore = sumSatisfaction
        
        return highScore

class Solution:
    def maxSatisfaction(self, s: List[int]) -> int:
        total=res=0
        s.sort()
        while s and s[-1]+total>=0:
            total+=s.pop()
            res+=total
        return res

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        for i in range(1, len(satisfaction)):
            current = satisfaction[i]
            for j in range(i, 0, -1):
                satisfaction[j] = current*(j+1) + satisfaction[j-1]
            satisfaction[0] = max(satisfaction[0], current)
            
        return max(max(satisfaction), 0)
                
            
                
                


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse = True)
        length, res = len(satisfaction), 0
        l = [0] * length
        
        for i in range(length):
            summ = 0
            for j in range(i + 1):
                l[j] += satisfaction[j]
                summ += l[j]
            
            if summ > res:
                res = summ
        
        return res

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        total = 0
        beneficial = [s for s in satisfaction if s >= 0]
        negative = [s for s in satisfaction if s < 0] # [-3, -1, ...]
        
        # any satisfaction >= 0 should be prepared
        # need to figure out when to include negative dishes
        # a negative dish increments the time coefficient, so it should be included if the difference 
        # between
        
        # a negative dish is beneficial if the satisfaction increases after adding it
        for s in reversed(negative):
            if calc_satisfaction([s] + beneficial) > calc_satisfaction(beneficial):
                beneficial.insert(0, s)
        
        return calc_satisfaction(beneficial)

    
def calc_satisfaction(dishes):
    total = 0
    for i,s in enumerate(dishes):
        total += (i+1) * s
    return total


class Solution:
    def maxSatisfaction(self, sat: List[int]) -> int:
        if (max(sat)<0):
            return 0
        arr = []
        sat.sort(reverse=True)
        for i in range(len(sat)):
            sun = 0
            for j in range(len(sat)-i):
                sun += sat[j]*(len(sat)-i-j)
            arr.append(sun)
        print(arr)
        return max(arr)

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()    
        bestSat = float('-inf')
        for i in range(len(satisfaction)):
            n = len(satisfaction)-1
            numItems = i+1
            numAdded = 0
            currSat = 0
            while numAdded <= numItems:
                currSat += satisfaction[n-numAdded]*(numItems-numAdded)
                numAdded += 1
            bestSat = max(bestSat,currSat)
        return max(bestSat,0)

def merge(arr1,arr2):
    index1,index2=0,0
    res=[]
    while index1 < len(arr1) or index2 < len(arr2):
        if index1 >= len(arr1) or (index2 < len(arr2) and arr1[index1] > arr2[index2]):
            res.append(arr2[index2])
            index2+=1
        else:
            res.append(arr1[index1])
            index1+=1
    return res

def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    m = int(len(arr)/2)
    return merge(mergeSort(arr[:m]),mergeSort(arr[m:]))

def splitAtZero(sortedArr):
    for i in range(len(sortedArr)):
        if sortedArr[i] >= 0:
            return (sortedArr[:i],sortedArr[i:])
    return (sortedArr,[])

def coefficient(arr):
    res = 0
    for i in range(len(arr)):
        res += (i+1)*arr[i]
    return res

class Solution:
    def maxSatisfaction(self, unsortedSatisfaction: List[int]) -> int:
        satisfaction = mergeSort(unsortedSatisfaction)
        negative,nonnegative = splitAtZero(satisfaction)
        res = nonnegative[:]
        for dish in reversed(negative):
            attempt = [dish] + res[:]
            if coefficient(attempt) > coefficient(res):
                res = attempt[:]
            else:
                return coefficient(res)
        return coefficient(res)


class Solution:

    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        temp = [0] * len(satisfaction)
        output = 0
        satisfaction.sort()
        print(satisfaction)
        for i, _ in enumerate(satisfaction):
            print((satisfaction[i:]))
            for j, s in enumerate(satisfaction[i:]): 
                temp[i] += s*(j+1)
            print((i, temp[i]))

        print(temp)
        for s in temp: 
            if s > output: 
                output = s

        return output


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        if satisfaction[-1] <= 0:
            return 0
        last_sum = 0
        temp = [0]*len(satisfaction)
        for i in range(len(satisfaction), 0, -1):
            temp = [a+b for a,b in zip(temp,[0]*(i-1)+satisfaction[i-1:] )]
            score = sum(temp)
            if last_sum > score:
                break
            last_sum = score
            
            
        return last_sum

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        dp = [[0] * len(satisfaction) for i in range(len(satisfaction))]

        maxVal = 0

        for i in range(len(satisfaction)):
            count = 1
            tempM = 0
            for j in range(i, len(satisfaction)):
                dp[i][j] = satisfaction[j] * count
                tempM += dp[i][j]
                count += 1
            maxVal = max(maxVal, tempM)
        return maxVal

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        sortlist = sorted(satisfaction, reverse=True)
        a=0
        b=0
        for i in range(len(sortlist)):
            a += sortlist[i]
            if a <= 0:
                break
            else:
                b+=1
        return sum(sortlist[j]*(b-j) for j in range(0,b))


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        m = 0
        while len(satisfaction) > 0:
            s = sum((satisfaction[i] * (i+1) for i in range(len(satisfaction))))
            m = max(s, m)
            satisfaction = satisfaction[1:]
        return m

import numpy as np

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        
        output = []
        length = len(satisfaction)
        satisfaction_srt = sorted(satisfaction)
        
        for i in range(length):
            satisfaction = satisfaction_srt[i:]
            time = list(range(1,length+1-i))
            output.append(np.dot(time,satisfaction))
        
        if max(output) < 0:
            return 0
        else:
            return max(output)
        
ans = Solution()
ans.maxSatisfaction([-1,-8,0,5,-7])

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        
        satisfaction=sorted(satisfaction)
        ans=0
        
        for i,s in enumerate(satisfaction):
            
            index=i
            curr_ans=0            
            j=1
            
            while index<=len(satisfaction)-1:
                curr_ans+=j*satisfaction[index]
                j+=1
                index+=1
                
            ans=max(ans,curr_ans)
        
        return ans
            


class Solution:
    def maxSatisfaction(self, satisfaction) -> int:
        n = satisfaction.__len__()
        if n == 0:
            return 0
        satisfaction.sort()
        if satisfaction[-1] <= 0 :
            return 0
        else:
            mannux = 0
            while satisfaction:
                tem = 0
                for i in range(n):
                    tem += (i+1)*satisfaction[i]
                if mannux< tem:
                    mannux= tem
                satisfaction.pop(0)
                n -= 1
            return mannux

class Solution:
    def maxSatisfaction(self, s: List[int]) -> int:
        s.sort(reverse = True)
        maxi = 0
        for i in range(len(s)):
            t = 0
            for j in range(i+1):
                t += s[j]*(i+1-j)
            maxi =max(maxi,t)
        return maxi

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        n = len(satisfaction)
        satisfaction.sort()
        ans = 0
        for i in range(n):
            coef = 0
            for k in range(1, n + 1):
                if i + k - 1 < n:
                    coef += satisfaction[i + k - 1] * k
            ans = max(ans, coef)
        return ans
                
        


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        
        sums = []
        temp = [0]*len(satisfaction)
        for i in range(len(satisfaction), 0, -1):
            temp = [a+b for a,b in zip(temp,[0]*(i-1)+satisfaction[i-1:] )]
            sums.append(sum(temp))
            
        result = max(sums)
        return result if result > 0 else 0

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        ordered_satis = sorted(satisfaction)
        nums = len_num = len(ordered_satis)
        max_satis = 0
        while len_num > 0:
            tem_max = 0
            for i, j in enumerate(ordered_satis):
                if nums - len_num > i:
                    continue
                tem_max += (i + 1 + len_num - nums) * j
            max_satis = max(max_satis, tem_max)
            len_num -= 1
        return max_satis

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        max_satisfaction = 0
        satis = 0
        sum_ = 0
        for s in satisfaction:
            satis += sum_ + s
            sum_ += s
            max_satisfaction = max(max_satisfaction, satis)
            if sum_ < 0:
                break
                
        return max_satisfaction


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        table = [[None]*len(satisfaction) for i in range(len(satisfaction))]
        for i in range(len(satisfaction)):
            for j in range(i,len(satisfaction)):
                table[i][j] = satisfaction[j]*(i+1)
        bestSat = float('-inf')
        for i in range(len(satisfaction)):
            row = i
            col = len(satisfaction)-1
            currSat = 0
            while row >= 0:
                currSat += table[row][col]
                row -= 1
                col -= 1
            bestSat = max(bestSat,currSat)
        return max(bestSat,0)

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        n = len(satisfaction)
        dp = [-1000000009]*(n+1)
        dp[0] = 0
        for i in range(n):
            for j in range(i, -1, -1):
                dp[j+1] = max(dp[j+1], satisfaction[i]*(j+1) + dp[j])
        answer = -1000000009
        for i in range(n+1):
            answer = max(dp[i], answer)
        return answer


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        currmax = 0
        satsort = sorted(satisfaction)
        leng1 = len(satsort)
        
        for nn in range(leng1):
            satpart = satsort[nn:]
            leng2 = leng1 - nn
            time = [ii for ii in range(1, leng2 + 1)]
            
            coeff = []
            for ii in range(leng2):
                coeff.append(satpart[ii] * time[ii])
            cumul = [coeff[0]]
            for ii in range(1, leng2):
                cumul.append(cumul[ii - 1] + coeff[ii])
            for elem in cumul:
                if currmax < elem:
                    currmax = elem
        return currmax

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        table = [[None]*len(satisfaction) for i in range(len(satisfaction))]
        for i in range(len(satisfaction)):
            for j in range(len(satisfaction)):
                if i > j:
                    continue
                table[i][j] = satisfaction[j]*(i+1)
        bestSat = float('-inf')
        for i in range(len(satisfaction)):
            row = i
            col = len(satisfaction)-1
            currSat = 0
            while row >= 0:
                currSat += table[row][col]
                row -= 1
                col -= 1
            bestSat = max(bestSat,currSat)
        return max(bestSat,0)

class Solution:
    def maxSatisfaction(self, s: List[int]) -> int:
        s.sort()
        l = len(s)
        
        dp = [[0 for _ in range(l)] for _ in range(l)]

        for i in range(l):
            for j in range(l):
                if j <= i:
                    if j == 0:
                        dp[i][j] = (j+1) * s[i]

                    else:
                        dp[i][j] = dp[i-1][j-1] + (j+1) * s[i]

        print(max(dp[-1]))
        
        return max(max(dp[-1]), 0)

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        n=len(satisfaction)
        dp=[[-1e9]*n for i in range(n)]
        for i in range(n):
            for j in range(i+1):
                dp[i][j]=max((dp[i-1][j-1] if i-1>=0 and j-1>=0 else 0)+satisfaction[i]*(j+1),
                             dp[i-1][j])
        ret=max(dp[-1])
        return ret if ret>0 else 0

import numpy as np
class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        
        sums = []
        temp = [0]*len(satisfaction)
        for i in range(len(satisfaction), 0, -1):
            #temp = [a+b for a,b in zip(temp,[0]*(i-1)+satisfaction[i-1:] )]
            temp = np.add(temp, [0]*(i-1)+satisfaction[i-1:] )
            sums.append(np.sum(temp))
            
        result = max(sums)
        return result if result > 0 else 0

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        n=len(satisfaction)
        ans=[ [-1e9] * n for i in range(n)]
        for i in range(n):
            for j in range(i+1):
                ans[i][j] = max((ans[i-1][j-1] if i-1>=0 and j-1>=0 else 0)+satisfaction[i]*(j+1), ans[i-1][j])
        answer = max(ans[-1])
        return answer if answer>0 else 0


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        sat=sorted(satisfaction)
        # print(sat)
#         self.ans=0
        
#         def traverse(ind,sat,time,gain):
#             if(ind==len(sat)):
#                 self.ans=max(self.ans,gain)
#                 return 
#             traverse(ind+1,sat,time,gain)
#             traverse(ind+1,sat,time+1,gain+time*sat[ind])
        
#         traverse(0,sat,1,0)
        
        dp=[[-float('inf')]*(len(sat)+1) for i in range(len(sat)+1)]
        
        for i in range(len(sat)+1):
            dp[0][i]=0
        
        # for i in dp:
        #     print(i)
        
        ans=0
        
        for i in range(1,len(sat)+1): # time
            for j in range(i,len(sat)+1):  # items
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+sat[j-1]*i)
                ans=max(ans,dp[i][j])
            
                
#         print(\"after\")
#         for i in dp:
#             print(i)
                
                
                
    
        return ans

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        sat=sorted(satisfaction)
        
        dp=[[-float('inf')]*(len(sat)+1) for i in range(len(sat)+1)]
        
        for i in range(len(sat)+1):
            dp[0][i]=0
        
        # for i in dp:
        #     print(i)
        
        ans=0
        
        for i in range(1,len(sat)+1): # time
            for j in range(i,len(sat)+1):  # items
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+sat[j-1]*i)
                ans=max(ans,dp[i][j])
            
                
#         print(\"after\")
        # for i in dp:
        #     print(i)
                
        return ans

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        totalDishes = len(satisfaction)
        
        dp = {}
        
        def cookOne(i0, n0):
            if i0 == totalDishes:
                return 0
            if (i0, n0) in dp:
                return dp[(i0, n0)]
            if satisfaction[i0] >= 0:
                dp[(i0, n0)] = (n0+1)*satisfaction[i0] + cookOne(i0+1, n0+1)
            else:
                dp[(i0, n0)] = max((n0+1)*satisfaction[i0] + cookOne(i0+1, n0+1), cookOne(i0+1, n0))
            
            return dp[(i0, n0)]
        
        return cookOne(0, 0)


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        res = total = 0
        i=len(satisfaction)-1
        satisfaction.sort()
        while i>=0 and satisfaction[i]+total > 0:
            total += satisfaction[i]
            res += total
            i-=1
        return res


class Solution:
    def maxSatisfaction(self, s: List[int]) -> int:
        s.sort()
        n = len(s)
        dp = [0] * (n+2)
        
        for dish in range(n-1, -1, -1):
            maxT = n+1
            for time in range(1, maxT):
                if dish == n-1:
                    dp[time] = time * s[dish]
                else:
                    include = time * s[dish] + dp[time + 1]
                    dp[time] = max(include, dp[time])
            maxT -= 1
        
        return max(0,dp[1])
        


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        @lru_cache(None)
        def dp(i, time):
            if i == len(satisfaction):
                return 0
            
            return max(time * satisfaction[i] + dp(i+1, time+1), dp(i+1, time))
        
        return dp(0, 1)

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        n = len(satisfaction)
        dp = [[0 for j in range(n + 1)] for i in range(n + 1)]
        for j in range(1, n + 1):
            dp[1][j] = satisfaction[j - 1]
        ans = 0
        for i in range(2, n + 1):
            for j in range(i, n + 1):
                dp[i][j] = dp[i - 1][j - 1]+satisfaction[ j -1] * i
                
                ans = max(ans, dp[i][j])
        
        return ans
                
        


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        n = len(satisfaction)
        import functools
        @functools.lru_cache(None)
        def DP(i,j):
            if i == n:
                return 0
            return max(satisfaction[i]*j + DP(i+1,j+1),DP(i+1,j))
        return DP(0,1)

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        @lru_cache(None)
        def dp(i, k):
            if i == len(satisfaction):
                return 0
            return max(dp(i+1, k), dp(i+1, k+1) + satisfaction[i] * k)
        return dp(0, 1)

def merge(arr1,arr2):
    index1,index2=0,0
    res=[]
    while index1 < len(arr1) or index2 < len(arr2):
        if index1 >= len(arr1) or (index2 < len(arr2) and arr1[index1] > arr2[index2]):
            res.append(arr2[index2])
            index2+=1
        else:
            res.append(arr1[index1])
            index1+=1
    return res

def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    m = int(len(arr)/2)
    return merge(mergeSort(arr[:m]),mergeSort(arr[m:]))

def splitAtZero(sortedArr):
    for i in range(len(sortedArr)):
        if sortedArr[i] >= 0:
            return (sortedArr[:i],sortedArr[i:])
    return (sortedArr,[])

def coefficient(arr):
    res = 0
    for i in range(len(arr)):
        res += (i+1)*arr[i]
    return res

class Solution:
    def maxSatisfaction(self, unsortedSatisfaction: List[int]) -> int:
        satisfaction = mergeSort(unsortedSatisfaction)
        # negative,nonnegative = splitAtZero(satisfaction)
        # res = nonnegative[:]
        # for dish in reversed(negative):
        #     attempt = [dish] + res[:]
        #     if coefficient(attempt) > coefficient(res):
        #         res = attempt[:]
        #     else:
        #         return coefficient(res)
        runningSum = 0
        for i in reversed(list(range(len(satisfaction)))):
            runningSum += satisfaction[i]
            if runningSum <= 0:
                return coefficient(satisfaction[i+1:])
        return coefficient(satisfaction)