1. The citizens of Antarctica on a future, slightly warmer planet, live in n cities along the coast of the continent. To get from one city to another they may sail, but the seas are rough and the voyage is slow. They have the idea to lay some roads across the uninhabited interior of the continent. Unfortunately they have not yet invented the traffic light, nor the tunnel nor the bridge, so these roads must be nonintersecting. Multiple roads can, however, leave the same city. (Also, although it doesn't matter much, you may suppose that melting of the glaciers has made the continent essentially round and flat.) The cities are labeled 1,...,n by their position in clockwise order around the coast. For each unordered pair {i,j} the government of Antarctica estimates a certain benefit Bij 2 0 that will be derived from building a road between cities i,j (1