Tom, a young explorer, visited an Indian tribe and fell in love with the Chief's daughter.
Tom asked the Chief to marry his daughter to him. But the Chief would accept his proposal
only if he could provide 10000 golden coins as the engagement gift. Tom couldn't make it,
so he pled for a reduction. The Chief said:" OK, I would then request 8000 golden coins
if you could get me the fur coat of the Pontiff. Or, if you could get me his crystal, I
could drop to 5000 golden coins."
Tom then went to the Pontiff for his fur coat
or crystal. The Pontiff too requested
some amount of golden coins as the exchange, or a possible reduction of price
if Tom could get him some other things. Tom continued to visit other people and
found that all of them would either request some golden coins for exchange, or
drop the price down for something else.
Now Tom needs your help on trading to marry the girl he loves.
An important rule Tom has to tell you is: the hierachical system is so strict
in this tribe that two people will never contact each other in any way if the
difference of the two levels they belong to is larger than a certain threshold.
Tom is an outsider so he is beyond this restriction. However, if he trades with
someone in a lower level, then others in a higher level will not trade with him
anymore since otherwise they would be indirectly contacting the lower levels,
and vice versa. Therefore your best suggestion to him must have all the situations
For the sake of convenience, let us mark all the trading objects by numbers starting
from 1. The Chief's approval is as well considered an object and is always marked
1. Each object has a price P, the owner's level L, and a sequence of substitutions
Ti and the corresponding "voucher" price Vi. There must be no "indirect trading"
if the difference between two levels is greater than M. You must calculate the
least number of golden coins Tom needs to marry the daughter of the Chief.