Your company has recently built its own highway from which they hope to generate some revenue. The highway has no branches or intersections, it is a simple line segment. Your company also has access to simple data from some potential customers that describe their start and endpoint locations and their budget.

Tollbooths are also located on various locations on the highway. The total toll a customer pays is the sum of all tolls on the tollbooths that lie between their start and end locations. If a customer cannot afford the total toll they must pay, then they simply don't make the trip and end up paying nothing.

The customer wants to start or end their destination at the precise location of a tollbooth, so we can represent the problem as follows. We have a graph that is a simple path with N nodes. Each node represents a potential start or end location of a customer and there is a single tollbooth located on each node. So the total toll a customer pays is the sum of the tolls on the nodes they cross to reach their endpoint. Both the start point and end point are also toll booths.

Your task is to set the tolls on each of the tollbooths to generate the maximum revenue for your company. The answer is the pricing of each toll booth.