The Manhattan Tourist Problem is a typical example in Dynamic Programming which is also used in Bioinfor$-$ matics to describe the DNA sequence alignment.

The problem involves a sightseeing tour in Manhattan, New York City from the corner of the ith street and jth Avenue to an attraction point i$.$e$.$ Chrysler Building at the $42$nd Street and Lexington Avenue. The tourists can travel only to the South and to the East directions. They can reach the destination from several ways but they want to maximize their benefit from this travel by visiting as many attraction points as possible. Each move they make has a benefit and they want to maximize their gain through the overall path.

Figure $1$: The Manhattan Tourist Problem on $55$ grid.

Using a structure called

struct node $*\{$ struct node $*$ south ; int south$\_$benefit; struct node $*$ east ; int east$\_$benefit;

$\}$

write a C program that maximizes the benefit from the uppermost left corner to the lowermost right on a $55$ grid in the above Figure $.$ Using a structure called

$```$

struct node $*\{$

struct node $*$ south ;

int south$\_$benefit;

struct node $*$ east ;

int east$\_$benefit;

$\}$

$```$

write a C program that maximizes the benefit from the uppermost left corner to the lowermost right on a $\backslash (5\backslash$times $5\backslash )$ grid in the above Figure $.$