A company is considering 5 projects. Each approved project will be completed over a 3-year period. Annual expenses and the final return for each project are shown below (in thousand dollars):

The company must choose the projects with the aim of maximizing total yields. In addition, the following information is available:

1. Projects 3 and 5 cannot be approved together.
2. If neither Project 4 nor 5 is selected, Projects 1 and 2 must be selected.
3. The company’s available annual capital is $25000, but it must reduce its expenditure by $5000 in one of the 3 years (i.e., can spend up to $20000 in that year) and that particular year must be also selected to maximize profits.

What projects must be selected and in which year $5000 must be saved?
 

Project 1 2 3 4 5 Expenses Year 1 5 4 3 7 8 Year 2 1 7 9 4 6 Year 3 8 10 2 1 10 Yields 20 40 20 15 30