Strawberries at the Going Price

A grower sells punnets of strawberries at a busy farmers' market. There are dozens of other stalls, so she is a price taker: she can sell as many punnets as she brings at the market price price (dollars), and none above it.

costs[q] is her total cost, in dollars, of picking and bringing q punnets, for q = 0, 1, ..., n (she cannot bring more than n). costs[0] is the stall rent, already paid for the day: she pays it whether she brings anything or not. Her profit from q punnets is

so bringing nothing gives \pi(0) = -C(0), a loss of the rent.

The rest of the cost, C(q) - C(0), is the variable cost, and \dfrac{C(q) - C(0)}{q} is the average variable cost of q punnets. If the price is below the lowest average variable cost, every punnet she brings loses money on top of the rent, so she brings none: that lowest average variable cost is her shutdown price.

Write best_output(costs, price) that returns a tuple (q, profit, shutdown):

1. q: the number of punnets (between 0 and n) with the highest profit; if several tie, the smallest;
2. profit: that highest profit (negative for a loss);
3. shutdown: the lowest average variable cost over q = 1..n.

Examples

Input:  costs = [40, 52, 60, 70, 84, 104, 130], price = 25
Output: (5, 21, 10.0)
Explanation: profits for q = 0..6 are -40, -27, -10, 5, 16, 21, 20.

Input:  costs = [40, 52, 60, 70, 84, 104, 130], price = 16
Output: (4, -20, 10.0)
Explanation: every output loses money, but 4 punnets lose only 20, half the rent.
The price is above the shutdown price of 10, so she still comes to market.

Input:  costs = [40, 52, 60, 70, 84, 104, 130], price = 14
Output: (3, -28, 10.0)
Explanation: 3 and 4 punnets both lose 28; the smaller output is returned.

Goals

• Choose the output that maximises profit when the price is given
• Treat a fixed cost that is already paid as part of every option, including producing nothing
• Find the shutdown price, the lowest average variable cost