Problem Statement

Weighted Non-Crossing Bridges Two neighbouring islands — North Island and South Island — each have a row of grain processing factories, listed from top to bottom. Every factory processes one grain type, written as an uppercase letter A – Z (for instance R for Rice, W for Wheat). You may build bridges between the two rows, subject to three rules: a bridge joins a North factory and a South factory of the same grain type; every factory takes part in at most one bridge; no two bridges may cross . Bridges are drawn as straight lines between the two rows, so if a bridge joins North factory i with South factory j , and another joins North factory i' with South factory j' , then i < i' must imply j < j' . Each grain type carries a profit: a bridge of grain type t earns profit[t] . Different types may be worth wildly different amounts, so the best plan is not always the one with the most bridges. Report the largest total profit achievable by a legal set of bridges. Building no bridges at