When Being Late Costs More

A pizza shop prints one promised delivery time c (in minutes) on every order. From its log of real delivery times times it knows what a promise would have cost:

• a pizza that takes t > c minutes is late, and every late minute costs late pence in vouchers;
• a pizza that takes t < c minutes arrives early, but every minute the promise was longer than needed costs early pence, because customers who see a long promise order elsewhere.

So a promise c costs late * (t - c) for each late pizza plus early * (c - t) for each early one, summed over the log.

Write best_promise(times, late, early) that returns a tuple (c, cost): the promise with the smallest total cost (the promise may be any number) and that cost. If several promises share the smallest cost, return the smallest of them.

Examples

Input:  times = [20, 25, 30, 35, 60], late = 3, early = 1
Output: (35, 105)
Explanation: at 35 the only late pizza costs 3 * 25 = 75 and the early ones 15 + 10 + 5 = 30.
A promise of 30 would cost 3 * (5 + 30) + (10 + 5) = 120; one of 60 would cost 130.

Input:  times = [10, 20], late = 1, early = 1
Output: (10, 10)
Explanation: every promise from 10 to 20 costs 10; the smallest is 10.

Constraints

• 1 <= len(times) <= 10**5; times are whole numbers from 1 to 10**4
• late and early are whole numbers from 1 to 100
• the answer c is a whole number and cost is an exact whole number

Goals

• Minimise a loss that punishes under- and over-prediction differently
• See that the best constant moves from the median towards a higher percentile when late is expensive
• Evaluate a piecewise linear loss at every candidate with running sums