The Island Tomato Exchange

On an island, restaurants buy tomatoes from growers through one exchange. Prices P are in dollars per crate, quantities in crates a week.

• Restaurant i has a rule (a, b): it wants a - b \cdot P crates, or 0 when that is negative (from its choke price a / b up).
• Grower j has a rule (m, s): it offers nothing at prices up to its minimum price m, and s \cdot (P - m) crates above it.

Market demand at a price is the sum over all restaurants, market supply the sum over all growers. Because each rule switches on or off at its own price, the two totals are lines with bends (kinks), and no single straight-line formula describes them over all prices.

Write clearing_price(buyers, sellers) that returns (price, quantity): the price at which market demand equals market supply with a positive quantity, and that quantity. If there is no such price (every grower's minimum price is at or above every restaurant's choke price), return None. When a price exists, it is the only one.

Examples

Input:  buyers = [(60, 2), (40, 4)], sellers = [(5, 3), (12, 2)]
Output: (14.142857142857142, 31.714285714285715)
Explanation: above 10 dollars the second restaurant buys nothing, and above 12 both
growers sell: 60 - 2P = 3(P - 5) + 2(P - 12) gives P = 99 / 7.

Input:  buyers = [(20, 2)], sellers = [(10, 5)]
Output: None
Explanation: the restaurant stops buying at 10 dollars, exactly where the grower starts.

Input:  buyers = [(100, 2)], sellers = [(4, 3)]
Output: (22.4, 55.2)

If you write helpers demand(p) and supply(p) for the two totals, press Run with ps = [p / 2 for p in range(61)], plot([demand(p) for p in ps], ps) and plot([supply(p) for p in ps], ps) to see the bends.

Constraints

• answers are compared with a tolerance of 1e-6 (relative or absolute)

Goals

• Build market demand and market supply from many individual rules, each with a kink at zero
• Find the price where the two totals are equal when no single formula covers the whole range
• Decide when no price gives a positive quantity