In a city, the rents of apartments change every month according to the demand. If there are x apartments in the city, all the rents for 12 months are given for each apartment and also x one time relocation prices are given(Applies when you move from one apartment to other in the first month).

If a person comes to this city and wants to rent an apartment, optimize the rental cost for whole year by generating a month wise plan on where he must stay each month?