The Prize Today or Later

Noor won a photo competition, and the sponsor offers several ways to take the prize. A euro today is worth more than a euro next year, because a euro today can be put in the bank at interest rate r (for example 5 % is r = 0.05) and will have grown to 1 + r euros a year from now. Turned around, a payment of P euros t years from now is worth

today: its present value. The present value of a stream of payments is the sum of the present values of its payments.

offers is a dict name -> payments, where payments[t] is paid t years from today; payments[0] is paid today and is not discounted. A payment can be negative (a fee Noor must pay). Write prize(offers, r) that returns a tuple (name, value): the offer with the highest present value, and that present value.

Examples

Input:  offers = {"lump sum": [1000], "four years": [0, 300, 300, 300, 300]}, r = 0.05
Output: ('four years', 1063.78515125)
Explanation: 300/1.05 + 300/1.05**2 + 300/1.05**3 + 300/1.05**4 = 1063.79 > 1000.

Input:  the same offers, r = 0.1
Output: ('lump sum', 1000.0)
Explanation: at 10 % the four payments are worth only 950.96 today.

Input:  offers = {"lump sum": [1000], "later": [0, 0, 0, 1300], "fee first": [-200, 400, 400, 400]}, r = 0.08
Output: ('later', 1031.98191333)

Constraints

• no two offers have present values within 1e-6 of each other, so there are no ties
• the value is compared with a tolerance of 1e-6

Goals

• Discount a payment $t$ years away by dividing it by $(1 + r)^t$
• Add up the present values of a stream of payments
• Compare offers with different timing on one common scale, money today