<p>A chef has collected data on the <code>satisfaction</code> level of his <code>n</code> dishes. Chef can cook any dish in 1 unit of time.</p>

<p><strong>Like-time coefficient</strong> of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. <code>time[i] * satisfaction[i]</code>.</p>

<p>Return the maximum sum of <strong>like-time coefficient </strong>that the chef can obtain after preparing some amount of dishes.</p>

<p>Dishes can be prepared in <strong>any </strong>order and the chef can discard some dishes to get this maximum value.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> satisfaction = [-1,-8,0,5,-9]
<strong>Output:</strong> 14
<strong>Explanation:</strong> After Removing the second and last dish, the maximum total <strong>like-time coefficient</strong> will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> satisfaction = [4,3,2]
<strong>Output:</strong> 20
<strong>Explanation:</strong> Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> satisfaction = [-1,-4,-5]
<strong>Output:</strong> 0
<strong>Explanation:</strong> People do not like the dishes. No dish is prepared.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == satisfaction.length</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>-1000 &lt;= satisfaction[i] &lt;= 1000</code></li>
</ul>

#define min_pq priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
#define vishal_mishra ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define print(x) { cout << x << "\n"; }
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define read(arr) for(auto& it : arr) cin >> it;
#define printit(arr) for(auto& it : arr) cout << it << " "
#define fl(i, a, b) for (ll i = a; i < b; i++)
#define f0(i, a, b) for (ll i = a; i <= b; i++)
#define rfl(i, a, b) for (ll i = a; i >= b; i--)
#define c4(x, y, z, w) cin >> x >> y >> z >> w
#define c3(x, y, z) cin >> x >> y >> z 
#define c6(x,y,z,w,s,t) cin >> x >> y >> z >> w >> s >> t
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
const ll inf = 1e10;
#define ff first
#define ss second
#define nl '\n'
#define comp(x) sort(x.begin(), x.end())
#define compr(x) sort(x.rbegin(), x.rend())
#define pb push_back
const ll maxn = 1000000;
vector<int> prime_one(maxn + 1, 0);
#define sz(a) (ll)a.size()
vector<int> con;
const ll MOD = 998244353;
using pii = pair<ll, ll>;
using vvi = vector<vi>;
using vii = vector<pii>;
using vvii = vector<vii>;
#define gap " "
#define lld long double
class Solution {
public:
    int maxSatisfaction(vector<int>& s) {
        ll n = s.size();

       comp(s);

        ll ct = 0;

        // for(int i=n-1;i >= 0 && satisfaction[i] > 0;i--) {
        //     ct += i*1ll*satisfaction[i];
        // }

        ll sum = s[n-1]; ll val = s[n-1]; ll max = val;

        rfl(i,n-2,0) {
            sum += s[i]; cout << sum << "s";
            val += sum;
            if(val > max) {
                max = val;
            }
            cout << val << " ";
        }
        return max < 0 ? 0 : max;

    }
};
14900