A firm has just discovered that, for the next five months, it will have an insufficient supply of warehouse space. The additional space requirements for the next five months are shown in Table $1$

To meet its requirements, the firm plans to lease additional space on a short$-$term basis. At the beginning of each month, the firm can lease any amount of square feet for any number of months. Separate leases can be taken out for different amounts of space and$/$or different lengths of time. For example, it might lease $5000$ square feet for $2$ months and another $10,000$ square feet for $3$ months. Also, new leases may be taken out before old ones expire. The cost per thousand square feet for leases of various lengths are given by Table $2$

Formulate a linear program whose solution will provide a leasing policy that satisfies the space requirement at minimum cost. $($Hint: You will need $15$ decision variables, one for each possible combination of the month in which the lease originates and the month in which the lease expires.$)$