Suppose you are given a directed, weighted graph G, and a source s and target t. You want to remove edges from the graph so that you cannot reach t from s. Each edge has a different cost associated with removing it; and on top of this per?edge cost, you must pay an additional $1 for every edge you remove. (E.g. if you remove edges with costs $4, $2, $3, you must pay a total of $4 + 2 + 3 + 1 + 1 + 1 = $12). Design an algorithm to find the cost of the cheapest set of edges to remove so that you disconnect s from t.

Hint: Think about how to modify the graph so that the cost of a min-cut reects its total cost.