There are n cities where for each i < j, there is a road from city i to city j which takes Tij time to travel. Two travelers Marco and Polo want to pass through allthe cities, in the shortest time possible. In the other words, we want to divide the cities into two sets and assign one set to Marco and assign the other one to Polo such that the sum of the travel time by them is minimized. You can assume they start their travel from the city with smallest index from their set, and they travel cities in the ascending order of index (from smallest index to largest). Design a dynamic programming algorithm that outputs the minimum total travel time and the partition. The time complexity of your algorithm should be O(n^2). Please write pseudo code.