class Solution:
    # initial thoughts: this seems like DP....
    # probably bottom-up though right? Idk let's see
    #
    # base case is if there's one task, the min amount of energy is the minimum
    #
    # so let's define the subproblem in terms of index i,
    # where the value is the minimum amount of energy to finish up to and including task i
    #
    # i = 0: then it's just minimum[i]
    # i = 1: it's min of
    #   do 0 then 1, so we start with minimum[0], use up actual[0]
    #   and now we need minimum[1], so it's minimum[1] - (minimum[0] - actual[0])
    #   or we could do 1 and then 0, minimum[0] - (minimum[1] - actual[1])
    # i = 2: we have the results of the first two, so it's analogous?
    #   do 2, then 0 and 1, or,
    #   do 0 and 1, then 2.
    # the subproblem result is the minimum for [0,1], the actual is just the sum of actual[0] and actual[1].
    # there are n! permutations of tasks, need to reduce this search space


        # dp = [float('inf') for i in range(n)]
        # for i in range(n):
        #     if i == 0:
        #         dp[i] = minimum[0]

        #     else:
        #         # do [0...i-1], then i

        #         # do i, then [0...i-1]

        #         # issue, what if i is somewhere in the middle? This doesn't cover all possibilities.

        #         # okay so what if we do graph search?
        #         # we consider all possible nodes
        #         # each node contains task index i and amount of energy
        #         # cost to travel an edge is actual[i]
        #         # edges only exist based on minimum[i]
        #         # yeah this will do it surely.

    # ok so graph search idea
    # task i can go to all other tasks j if
    # the node has enough energy

    # the max amount of energy necessary is bounded by the sum of all minimum[i]
    # let's say we start there
    # we do a APSP using Floyd Warshall
    # find the min weight SP? but this is more like a spanning tree since we must hit every task
    #
    # I think it's MST but the edges are weighted by the additional energy necessary.
    # it's a directed graph, the logic above (pasted here)
    #    do 0 then 1, so we start with minimum[0], use up actual[0]
    #    and now we need minimum[1], so it's minimum[1] - (minimum[0] - actual[0])
    #    or we could do 1 and then 0, minimum[0] - (minimum[1] - actual[1])
    # is sorta repeatable - we can travel from 0 to 1, or 1 to 0. The cost from 0 to 1 is
    # minimum[1] - (minimum[0] - actual[0]), and it's assumed you have minimum[0] to start.
    # Then we just do a minimum spanning tree? But the issue is the edges are directed so it's a little more annoying.
    # the edges being directed and having to hit all vertices implies some sort of priority first search maybe?
    #
    # it's so hard to figure out what the graph should be, maybe it is DP after all?
    # and my subproblems just suck?
    # I guess technically there are 0 to i-1 solved before,
    # so there are i places to insert task[i],
    # but the number of subproblems blow up in terms of subsets.
    #
    # i guess it might be sort of resembling coin change?
    # it could be a binary search DP. We know the maximum answer is the sum of the minimums[0...n]
    # so we can start at halfway, if that's possible we guess down, otherwise we guess up?
    # but that's log n DPs... that probably sucks ass.
    #

    def minimumEffort(self, tasks: List[List[int]]) -> int:
        n = len(tasks)
        actual = []
        minimum = []
        for i in range(n):
            actual.append(tasks[i][0])
            minimum.append(tasks[i][1])

It could be doable to store states where the states contain the ones completed thus far, but then just this bitset is 2^n possible outcomes, which is surely not in time bounds (so this type of DP is infeasible)

oh shit you can't refill energy, you only start with a bunch. That drastically changes the problem.

Then the answer is lower bounded by the maximum value in the minimum array
and upper bounded by the sum of the actuals

        # bound_1 = sum(actual), need to be able complete all the tasks
        # bound_2 = max(minimum), need to be able to start all the tasks
        # answer lies somewhere in between

take the MST idea from earlier. since we assume taht minimum[i] >= actual[i],
the true cost of a node is (minimum[0] - actual[0]) for the zeroth node,

so the costs are all minimum[i] - actual[i].

oh wait do we just want to do the highest cost nodes first...

is it provable that this attains the minimum solution?
because a [1, 5] node costs more than a [13, 14] node,
but the 14 imposes a stricter requirement?
But anyways we'll need a lot more down the line...
oh shit THAT's where the DP subproblems are?

So the min cost of achieving all the previous is the sum of their minimum[i] - actual[i]?


no because that doesn't tell us where to insert the thing.

if we sum the costs that's naively wrong because in the case of
  [1, 5] and [13, 14] the sum of costs is 4 + 1 = 5, but ig if we added the max actual[i] = 13
  then we'd get 18 which is correct.

so ideally we get the highest cost nodes out of the way earlier,
but we also want to get the highest barrier to entry nodes out of the way earlier too (while we have energy to use)




also patently untrue, because it sometimes may be better to do a higher cost node if its actual[i] is low,
that way we preserve energy. So this somehow still feels like DP...




what if it's sort by cost, tiebreak by putting higher minimums last? but that makes no intuitive sense, you'd want higher minimums to come early on?





continuing the old DP logic
    # i = 0: then it's just minimum[i]
    # i = 1: it's min of
    #   do 0 then 1, so we start with minimum[0], use up actual[0]
    #   and now we need minimum[1], so it's minimum[1] - (minimum[0] - actual[0])
    #   or we could do 1 and then 0, minimum[0] - (minimum[1] - actual[1])
    # i = 2: min of
    #   do [0, 1], then 2
    #   do 2, then [0, 1]
    #   do 0, 2, 1
    #   do 1, 2, 0
    #
    #   So we reuse the i=1 for the subproblems
    #   but then we have to compute new permutations,
    #   the number of which is proportional to the number of tasks we've already done.
    #
    #
    #   this goes back to the subproblem states being a bitset of length n which gives 2^n states,
    #   but maybe the reuse is OK?
    #   I mean the issue is there aren't THAT many states right... fib(n) requires n states,
    #   it's just that they're reused a lot.
    #   but this already has an exponential number of states, and DP work is poly in # of states, so this can't be
    #
    #
    #
    #

For some reason I keep going back to MSTs in my mind.

if we used Kruskal's, we'd sort the edge weights and then try adding one by one

but what would the edges be for this graph so that I can find the MST?


If the n vertices are the n tasks,
the cost of an undirected edge is kinda nonsense...








I'm still thinking about the minimum[0] - actual[0] thing


the cost of a task is that we need to muster up the minimum energy to do it, and then expend the actual energy.

We'd want the high effort tasks first I guess. So we'll sort by cost then by high to low min energy.