Driven by recent erce competition in retail market, The Store, one of the largest department store
chains in Thailand starts a project to boost customer visiting. Since The Store has good relation with
Joy Boy", a talented superstar, The Store decided that having Joy Boy" perform concert once per
month is the best way to lure more customer to the store. The project last c months, hence, there will
be c Joy Boy concerts to be performed.
The Store has s department stores in different cities, one store per one city. Each city is numbered
from 1 to s. The Store has to decide which store should have the concert on each month. The planning
department of The Store has calculated, for every pair stores and months, the expected prot if Joy
Boy performs a concert on a particular store in a particular month. Being nice and all, Joy Boy does
not charge for his performance but he ask The Store to pay for his traveling and hotel expense. The
planning department also knows the traveling cost for every pair of stores. Of course, it is possible to
have Joy Boy stay at the same store for the next month and it might be some expense even though he
performs at the same store.
Be noted that Joy Boy does not charge the cost traveling to the rst concert. The Store asks you
to project the maximum possible prots minus traveling cost from Joy Boy's Thailand tour for The
Store.